Perron root of permanental compounds

← Minc’s list

Minc’s list · Problem 18

Perron root 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 18 in his 1987 survey.

Problem 18. Find an algorithm for the Perron root of the \(k\)th permanental compound of a given nonnegative square matrix.

For a nonnegative \(n\times n\) matrix \(A\), the \(k\)th permanental compound \(P_k(A)\), the \(\binom nk\times\binom nk\) matrix of all \(k\times k\) subpermanents, is nonnegative, so its spectral radius \(\rho(P_k(A))\) is an eigenvalue, the Perron root. Minc called it a key to the asymptotic growth of permanents of \((0,1)\)-circulants. Since \(P_n(A)=[\operatorname{per}A]\), no general exact polynomial-time method is expected, so the natural goals are faster exact methods for special classes and efficient approximation.

Prior progress

  • Brualdi and Newman (1966) showed that the compound of a row-substochastic matrix is row-substochastic, so its Perron root is at most \(1\). Minc (1987) proved \(\rho(P_k(A))\le\rho(A)^k\) and computed the Perron root exactly for a sparse class of companion matrices.
  • Al’pina and Al’pin (2004) compared permanental and determinantal compounds and bounded the Perron root, and the tropical eigenvalue bounds of Akian, Gaubert and Marchesini (2014) also give upper bounds.
  • Cheon and Wanless (2005) reported no progress, and we found no later general algorithm.

Our progress so far

  • Efficient approximation for broad classes. For every rational nonnegative \(A\) with positive diagonal, and for every rational symmetric (or diagonally symmetrizable) nonnegative \(A\), the Perron root \(\rho(P_k(A))\) has a fully polynomial randomized approximation scheme, uniformly in \(k\) and without forming \(P_k(A)\). This is an existence result; the scheme has not been implemented.
  • When the Perron root is zero. \(\rho(P_k(A))>0\) if and only if the support digraph of \(A\) has vertex-disjoint directed cycles covering at least \(k\) vertices, which can be checked in polynomial time.
  • Exact methods. For \(A\) of rank at most \(r\), the Perron root equals that of an explicit matrix whose size is polynomial in \(k\) for fixed \(r\); block-constant matrices reduce similarly. For \(k=2\) and any rational \(A\ge0\), we can compute rational bounds \(L\le\rho(P_2(A))\le U\) of any prescribed accuracy without forming \(P_2(A)\).
  • Log-concavity in \(k\). With \(\rho_k=\rho(P_k(A))\) and \(\rho_0=1\), we proved \(\rho_k^2\ge\rho_{k-1}\rho_{k+1}\) for \(0<k<n\), which gives \(\operatorname{per}(A)^{k/n}\le\rho_k\le\rho(A)^k\).

References

  1. H. Minc, Research problems: permanental compounds, Linear and Multilinear Algebra 19 (1986), 199–201.
  2. 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
  3. R. A. Brualdi and M. Newman, Inequalities for the permanental minors of non-negative matrices, Canad. J. Math. 18 (1966), 608–615. doi:10.4153/CJM-1966-059-5
  4. 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
  5. M. Akian, S. Gaubert and A. Marchesini, Tropical bounds for eigenvalues of matrices, Linear Algebra Appl. 446 (2014), 281–303. doi:10.1016/j.laa.2013.12.021