Header menu link for other important links
X
On the expressive power of read-once determinants
, P.S. Joglekar
Published in Springer Verlag
2015
Volume: 9210
   
Pages: 95 - 105
Abstract
We introduce and study the notion of read-k projections of the determinant: a polynomial f ∈ F[x1,…, xn] is called a read-k projection of determinant if f = det(M), where entries of matrix M are either field elements or variables such that each variable appears at most k times in M. A monomial set S is said to be expressible as read-k projection of determinant if there is a read-k projection of determinant f such that the monomial set of f is equal to S. We obtain basic results relating readk determinantal projections to the well-studied notion of determinantal complexity. We show that for sufficiently large n, the n × n permanent polynomial Permn and the elementary symmetric polynomials of degree d on n variables Sd n for 2 ≤ d ≤ n − 2 are not expressible as readonce projection of determinant, whereas mon(Permn) and mon(Sd n) are expressible as read-once projections of determinant. We also give examples of monomial sets which are not expressible as read-once projections of determinant. © Springer International Publishing Switzerland 2015.