Characteristic polynomial of permanental compounds

← Minc’s list

Minc’s list · Problem 17

Characteristic polynomial of permanental compounds

Open

Posed by
Minc
First posed
1986

Statement

Posed by H. Minc in a 1986 research-problems note on permanental compounds; it is Problem 17 in his 1987 survey.

Problem 17. Find an algorithm for the characteristic polynomial of the \(k\)th permanental compound of a given square matrix.

The \(k\)th permanental compound of an \(n\times n\) matrix \(A\) is the \(\binom nk\times\binom nk\) matrix \(P_k(A)\) of all its \(k\times k\) subpermanents \(\operatorname{per}A[\alpha\mid\beta]\). Unlike the determinantal compound, it is not multiplicative and its spectrum is not determined by that of \(A\). Building \(P_k(A)\) directly is possible but grows exponentially, so the aim is methods that do better; Minc needed them to derive recurrences for permanents of \((0,1)\)-circulants.

Prior progress

  • Minc (1987) described the compounds of nonnegative companion matrices and, for a sparse class of them, expressed their characteristic polynomials through the eigenvalues of a related matrix, which gives an effective answer for that class.
  • Bebiano, Li and da Providência (2000), and Al’pina and Al’pin (2004), located and compared the spectra of permanental compounds; these are bounds, not algorithms.
  • Cheon and Wanless (2005) reported no progress.

Our progress so far

  • A faster exact method for \(k=2\). We can compute \(\chi_{P_2(A)}\) exactly without forming \(P_2(A)\), in \(\tilde O(n^{\omega+2})\) field operations, against \(\tilde O(n^{2\omega})\) for the direct method.
  • Bounded rank, for every \(k\). If \(A\) has rank \(r\), then \(\chi_{P_k(A)}\) can be computed in time polynomial in \(n\) and \(k\) for fixed \(r\), although \(P_k(A)\) itself can have exponential size.
  • Block-constant matrices. If \(A\) is constant on the blocks of a partition into \(m\) row and \(m\) column classes, computing \(\chi_{P_k(A)}\) reduces to a determinant whose size depends only on \(m\) and \(k\), not on \(n\).

References

  1. H. Minc, Research problems: permanental compounds, Linear and Multilinear Algebra 19 (1986), 199–201.
  2. H. Minc, Theory of permanents 1982–1985, Linear and Multilinear Algebra 21 (1987), 109–148. doi:10.1080/03081088708817786
  3. H. Minc, Permanental compounds and permanents of (0,1)-circulants, Linear Algebra Appl. 86 (1987), 11–42. doi:10.1016/0024-3795(87)90285-0
  4. N. Bebiano, C.-K. Li and J. da Providência, Generalized numerical ranges of permanental compounds arising from quantum systems of bosons, Electron. J. Linear Algebra 7 (2000), 73–91. doi:10.13001/1081-3810.1048
  5. V. S. Al’pina and Yu. A. Al’pin, Permanental compound matrices and Schneider’s theorem, J. Math. Sci. 132 (2006), 147–152. doi:10.1007/s10958-005-0483-6