Symmetric Determinantal Representations in Characteristic 2

Bruno Grenet 1 Thierry Monteil 2 Stéphan Thomassé 1
2 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper studies Symmetric Determinantal Representations (SDR) in characteristic 2, that is the representation of a multivariate polynomial P by a symmetric matrix M such that P=det(M), and where each entry of M is either a constant or a variable. We first give some sufficient conditions for a polynomial to have an SDR. We then give a non-trivial necessary condition, which implies that some polynomials have no SDR, answering a question of Grenet et al. A large part of the paper is then devoted to the case of multilinear polynomials. We prove that the existence of an SDR for a multilinear polynomial is equivalent to the existence of a factorization of the polynomial in certain quotient rings. We develop some algorithms to test the factorizability in these rings and use them to find SDRs when they exist. Altogether, this gives us polynomial-time algorithms to factorize the polynomials in the quotient rings and to build SDRs. We conclude by describing the case of Alternating Determinantal Representations in any characteristic.
Type de document :
Article dans une revue
Linear Algebra and its Applications, Elsevier, 2013, 439 (5), pp.24. 〈10.1016/j.laa.2013.04.022〉
Liste complète des métadonnées

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00830871
Contributeur : Bruno Grenet <>
Soumis le : mercredi 5 juin 2013 - 19:02:29
Dernière modification le : jeudi 5 juillet 2018 - 15:42:51

Lien texte intégral

Identifiants

Citation

Bruno Grenet, Thierry Monteil, Stéphan Thomassé. Symmetric Determinantal Representations in Characteristic 2. Linear Algebra and its Applications, Elsevier, 2013, 439 (5), pp.24. 〈10.1016/j.laa.2013.04.022〉. 〈ensl-00830871〉

Partager

Métriques

Consultations de la notice

370