Matrix factorizations of determinants and permanents

From MaRDI portal





Let \( A \) be an \( n \)-square matrix with entries in the complex field. As usual \[ \operatorname{det}(A)=\sum_{\sigma \in S_{n}} \operatorname{sgn}(\sigma) \prod_{t=1}^{n} a_{t, \sigma(t)}, \quad \operatorname{per}(A)=\sum_{\sigma \in S_{n}} \prod_{t=1}^{n} a_{t, \sigma(t)} \cdot \] Observe that \[ \left[\begin{array}{ll} a_{1} & a_{2} \end{array}\right]\left[\begin{array}{r} b_{2} \\ \pm b_1 \end{array}\right]=\left\{\begin{array}{l} \operatorname{per}(A) \\ \operatorname{det}(A) \end{array}, A=\left[\begin{array}{ll} a_{1} & a_{2} \\ b_{1} & b_{2} \end{array}\right]\right. \] \[ \left[\begin{array}{lll} a_{1} & a_{2} & a_{3} \end{array}\right]\left[\begin{array}{rrr} b_{2} & b_{3} & 0 \\ \pm b_{1} & 0 & b_{3} \\ 0 & \pm b_{1} & \pm b_{2} \end{array}\right]\left[\begin{array}{r} c_{3} \\ c_{2} \\ c_{1} \end{array}\right]=\left\{\begin{array}{l} \operatorname{per}(A) \\ \operatorname{det}(A) \end{array}, A=\left[\begin{array}{lll} a_{1} & a_{2} & a_{3} \\ b_{1} & b_{2} & b_{3} \\ c_{1} & c_{2} & c_{3} \end{array}\right]\right. \] where the minus signs apply to \( \operatorname{det}(A) \). In this excellent paper the authors provide such a factorization of permanents and determinants for an arbitrary \( n \)-square matrix \( A \). The following is a sketch of the development of the permanent factorization. Let \( I=\left[\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right], E=\left[\begin{array}{ll}0 & 0 \\ 1 & 0\end{array}\right] \). Define \( E_{i}=I \otimes \ldots \otimes I \otimes \stackrel{i}{E} \otimes I \otimes \ldots \otimes I \) where \( \otimes \) denotes Kronecker product. Then \( E_{i} E_{j}=E_{j} E_{i}, i \neq j \), and \( E_{i}^{2}=0 \), \( i=1, \ldots, n \). Clearly \( \operatorname{per}(A) E_{1} \cdots E_{n}=\prod_{i=1}^{n} \sum_{j=1}^{n} a_{i j} E_{j} \). Next let \( X\left(a_{1}, \ldots, a_{n}\right)= \) \( a_{1} E_{1}+\cdots+a_{n} E_{n} \). By a suitable permutation matrix \( Q \), we can write \( \bar{Y}\left(a_{1}, \ldots, a_{n}\right)=Q X\left(a_{1}, \ldots, a_{n}\right) Q^{T} \) where \( a_{1} \) appears in the first column of \( Y, a_{2} \) in the second column \(, \ldots, a_{2}, \ldots, a_{n} \) appear in column \( 2^{n}-1 \) and \( a_{1}, \ldots, a_{n} \) appear in column \( 2^{n} \). Moreover \( a_{1}, \ldots, a_{n} \) appear in row 1 of \( Y, \ldots, a_{2} \) in row \( 2^{n}-1 \) and \( a_{1} \) in row \( 2^{n} \). Then \( \operatorname{per}(A) Q E_{1} \cdots E_{n} Q^{T}=\prod_{j=1}^{n} Y\left(a_{j 1}, \ldots, a_{j n}\right) \) where \( Y\left(a_{j 1}, \ldots, a_{j n}\right)=Q X\left(a_{j 1}, \ldots, a_{j n}\right) \). It can be shown that \(\operatorname{per} (A) \) appears as the \( \left(1,2^{n}\right) \) entry on the left side of (1). Next, partition \( Y \) into blocks \( Y_{k l}, k= \) \( n, \ldots, 0, l=0, \ldots, n \), where \( Y_{k l} \) is the \( \left(\begin{array}{l}n \\ k\end{array}\right) \times\left(\begin{array}{l}n \\ l\end{array}\right) \) submatrix of \( Y \) determined by the rows of \( Y \) with \( k \) non-zero entries and the columns with \( l \) non-zero entries. The authors show that \( Y_{k l}=0 \) unless \( k+l=n+1 \). If \( k+l=n+1 \), let \( Y_{k l}=P_{l} \). Then equating the \( \left(1,2^{n}\right) \) entries on both sides of (1), one obtains (2) per \( (A)= \) \( \prod_{i=1}^{n} P_{i}\left(a_{i 1}, \ldots, a_{i n}\right) \). Equation (2) is the factorization for permanents. A factorization for determinants is obtained in the same manner. From (2) it follows that (3) \( \|\operatorname{per}(A)\| \leq \prod_{i=1}^{n}\left\|P_{i}\left(a_{i 1}, \ldots, a_{i n}\right)\right\| \), where \(\|\|\) is the Euclidean norm. Using (3), the authors prove the following results: If \( A \) is an \( n \)-square \( (0,1) \) matrix with \( r_{i} \) ones in row \( i, i=1, \ldots, n \), then \[ \operatorname{per}(A) \leq \prod_{j=1}^{n}\left(r_{j}!\right)^{1 / n}\left(\frac{r_{j}+1}{2}\right)^{\left(n-r_{j}\right) / n} \] If \( A \) is an arbitrary \( n \)-square matrix with \( r_{i}=\sum_{j=1}^{n}\left|a_{i j}\right|, \quad q_{i}=\max _{i}\left|a_{i j}\right| \), \( i=1, \ldots, n \), then (4) \( |\operatorname{per}(A)| \leq \prod_{j=1}^{n}\left(\frac{r_{j}+q_{j}}{2}\right) \). If \( A \) is a \( (0,1) \) matrix, then \( q_{j} \leq 1 \) and hence (4) reduces to Minc's inequality per \( (A) \leq \prod_{j=1}^{n}\left(\frac{r_{j}+1}{2}\right) \).




Cited in
(27)








This page was built for publication: Matrix factorizations of determinants and permanents

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5920846)