Compound matrix

Template:Short description In linear algebra, a branch of mathematics, a (multiplicative) compound matrix is a matrix whose entries are all minors, of a given size, of another matrix. Compound matrices are closely related to exterior algebras, and their computation appears in a wide array of problems, such as in the analysis of nonlinear time-varying dynamical systems and generalizations of positive systems, cooperative systems and contracting systems.

Definition

Let Template:Math be an Template:Math matrix with real or complex entries.Template:Efn If Template:Math is a subset of size Template:Math of Template:Math and Template:Math is a subset of size Template:Math of Template:Math, then the Template:Math-submatrix of Template:Math, written Template:Math , is the submatrix formed from Template:Math by retaining only those rows indexed by Template:Math and those columns indexed by Template:Math. If Template:Math, then Template:Math is the Template:Math-minor of Template:Math.

The r th compound matrix of Template:Math is a matrix, denoted Template:Math, is defined as follows. If Template:Math, then Template:Math is the unique Template:Math matrix. Otherwise, Template:Math has size $(\genfrac{}{}{0ex}{}{m}{r})\times (\genfrac{}{}{0ex}{}{n}{r})$. Its rows and columns are indexed by Template:Math-element subsets of Template:Math and Template:Math, respectively, in their lexicographic order. The entry corresponding to subsets Template:Math and Template:Math is the minor Template:Math.

In some applications of compound matrices, the precise ordering of the rows and columns is unimportant. For this reason, some authors do not specify how the rows and columns are to be ordered.

For example, consider the matrix

$A=\left(\begin{array}{cccc}1& 2& 3& 4\\ 5& 6& 7& 8\\ 9& 10& 11& 12\end{array}\right).$

The rows are indexed by Template:Math and the columns by Template:Math. Therefore, the rows of Template:Math are indexed by the sets

$\{1,2\}<\{1,3\}<\{2,3\}$

and the columns are indexed by

$\{1,2\}<\{1,3\}<\{1,4\}<\{2,3\}<\{2,4\}<\{3,4\}.$

Using absolute value bars to denote determinants, the second compound matrix is

$\begin{array}{cc}{C}_2(A)& =\left(\begin{array}{cccccc}\left|\begin{array}{cc}1& 2\\ 5& 6\end{array}\right|& \left|\begin{array}{cc}1& 3\\ 5& 7\end{array}\right|& \left|\begin{array}{cc}1& 4\\ 5& 8\end{array}\right|& \left|\begin{array}{cc}2& 3\\ 6& 7\end{array}\right|& \left|\begin{array}{cc}2& 4\\ 6& 8\end{array}\right|& \left|\begin{array}{cc}3& 4\\ 7& 8\end{array}\right|\\ \left|\begin{array}{cc}1& 2\\ 9& 10\end{array}\right|& \left|\begin{array}{cc}1& 3\\ 9& 11\end{array}\right|& \left|\begin{array}{cc}1& 4\\ 9& 12\end{array}\right|& \left|\begin{array}{cc}2& 3\\ 10& 11\end{array}\right|& \left|\begin{array}{cc}2& 4\\ 10& 12\end{array}\right|& \left|\begin{array}{cc}3& 4\\ 11& 12\end{array}\right|\\ \left|\begin{array}{cc}5& 6\\ 9& 10\end{array}\right|& \left|\begin{array}{cc}5& 7\\ 9& 11\end{array}\right|& \left|\begin{array}{cc}5& 8\\ 9& 12\end{array}\right|& \left|\begin{array}{cc}6& 7\\ 10& 11\end{array}\right|& \left|\begin{array}{cc}6& 8\\ 10& 12\end{array}\right|& \left|\begin{array}{cc}7& 8\\ 11& 12\end{array}\right|\end{array}\right)\\ & =\left(\begin{array}{cccccc}-4& -8& -12& -4& -8& -4\\ -8& -16& -24& -8& -16& -8\\ -4& -8& -12& -4& -8& -4\end{array}\right).\end{array}$

Properties

Let Template:Math be a scalar, Template:Math be an Template:Math matrix, and Template:Math be an Template:Math matrix. For Template:Math a positive integer, let Template:Math denote the Template:Math identity matrix. The transpose of a matrix Template:Math will be written Template:Math, and the conjugate transpose by Template:Math. Then:

• Template:Math, a Template:Math identity matrix.
• Template:Math.
• Template:Math.
• If Template:Math, then Template:Math.
• If Template:Math, then $C_r(I_n)=I_{(\genfrac{}{}{0ex}{}{n}{r})}$.
• If Template:Math, then Template:Math.
• If Template:Math, then Template:Math.
• Template:Math, which is closely related to Cauchy–Binet formula.

Assume in addition that Template:Math is a square matrix of size Template:Math. Then:

• Template:Math.
• If Template:Math has one of the following properties, then so does Template:Math:
  • Upper triangular,
  • Lower triangular,
  • Diagonal,
  • Orthogonal,
  • Unitary,
  • Symmetric,
  • Hermitian,
  • Skew-symmetric (when r is odd),
  • Skew-hermitian (when r is odd),
  • Positive definite,
  • Positive semi-definite,
  • Normal.
• If Template:Math is invertible, then so is Template:Math, and Template:Math.
• (Sylvester–Franke theorem) If Template:Math, then $\det C_r(A)=(\det A{)}^{(\genfrac{}{}{0ex}{}{n-1}{r-1})}$.

Relation to exterior powers

Give Template:Math the standard coordinate basis Template:Math. The Template:Math th exterior power of Template:Math is the vector space

${\wedge }^r{𝐑}^n$

whose basis consists of the formal symbols

${𝐞}_{i_1}\wedge \dots \wedge {𝐞}_{i_r},$

where

$i_1<\dots <i_r.$

Suppose that Template:Math is an Template:Math matrix. Then Template:Math corresponds to a linear transformation

$A:{𝐑}^n\to {𝐑}^m.$

Taking the Template:Math th exterior power of this linear transformation determines a linear transformation

${\wedge }^{r}A:{\wedge }^r{𝐑}^n\to {\wedge }^r{𝐑}^m.$

The matrix corresponding to this linear transformation (with respect to the above bases of the exterior powers) is Template:Math. Taking exterior powers is a functor, which means that

${\wedge }^r(AB)=({\wedge }^{r}A)({\wedge }^{r}B).$

This corresponds to the formula Template:Math. It is closely related to, and is a strengthening of, the Cauchy–Binet formula.

Relation to adjugate matrices

Let Template:Math be an Template:Math matrix. Recall that its Template:Mvar th higher adjugate matrix Template:Math is the $(\genfrac{}{}{0ex}{}{n}{r})\times (\genfrac{}{}{0ex}{}{n}{r})$ matrix whose Template:Math entry is

$(-1{)}^{\sigma (I)+\sigma (J)}\det A_{J^c,I^c},$

where, for any set Template:Math of integers, Template:Math is the sum of the elements of Template:Math. The adjugate of Template:Math is its 1st higher adjugate and is denoted Template:Math. The generalized Laplace expansion formula implies

$C_r(A){\mathrm{adj}}_r(A)={\mathrm{adj}}_r(A)C_r(A)=(\det A)I_{(\genfrac{}{}{0ex}{}{n}{r})}.$

If Template:Math is invertible, then

${\mathrm{adj}}_r(A^{-1})=(\det A{)}^{-1}{C}_r(A).$

A concrete consequence of this is Jacobi's formula for the minors of an inverse matrix:

$\det (A^{-1}{)}_{J^c,I^c}=(-1{)}^{\sigma (I)+\sigma (J)}\frac{\det A_{I,J}}{\det A}.$

Adjugates can also be expressed in terms of compounds. Let Template:Math denote the sign matrix:

$S=\mathrm{diag}(1,-1,1,-1,\dots ,(-1{)}^{n-1}),$

and let Template:Math denote the exchange matrix:

$J=\left(\begin{array}{ccc}& & 1\\ & \cdots & \\ 1& & \end{array}\right).$

Then Jacobi's theorem states that the Template:Math th higher adjugate matrix is:

${\mathrm{adj}}_r(A)=J{C}_{n-r}(SAS{)}^{T}J.$

It follows immediately from Jacobi's theorem that

$C_r(A)J(C_{n-r}(SAS){)}^{T}J=(\det A)I_{(\genfrac{}{}{0ex}{}{n}{r})}.$

Taking adjugates and compounds does not commute. However, compounds of adjugates can be expressed using adjugates of compounds, and vice versa. From the identities

$C_r(C_s(A))C_r({\mathrm{adj}}_s(A))=(\det A{)}^{r}I,$

$C_r(C_s(A)){\mathrm{adj}}_r(C_s(A))=(\det C_s(A))I,$

and the Sylvester-Franke theorem, we deduce

${\mathrm{adj}}_r(C_s(A))=(\det A{)}^{(\genfrac{}{}{0ex}{}{n-1}{s-1})-r}{C}_r({\mathrm{adj}}_s(A)).$

The same technique leads to an additional identity,

$\mathrm{adj}(C_r(A))=(\det A{)}^{(\genfrac{}{}{0ex}{}{n-1}{r-1})-r}{C}_r(\mathrm{adj}(A)).$

Compound and adjugate matrices appear when computing determinants of linear combinations of matrices. It is elementary to check that if Template:Math and Template:Math are Template:Math matrices then

$\det (sA+tB)=C_n\left(\left[\begin{array}{cc}sA& I_n\end{array}\right]\right)C_n\left(\left[\begin{array}{c}{I}_n\\ tB\end{array}\right]\right).$

It is also true that:

$\det (sA+tB)=\sum _{r=0}^n{s}^r{t}^{n-r}\mathrm{tr}({\mathrm{adj}}_r(A)C_r(B)).$

This has the immediate consequence

$\det (I+A)=\sum _{r=0}^n\mathrm{tr}{\mathrm{adj}}_r(A)=\sum _{r=0}^n\mathrm{tr}{C}_r(A).$

Numerical computation

In general, the computation of compound matrices is non-effective due to its high complexity. Nonetheless, there are some efficient algorithms available for real matrices with special structure.

References

• Gantmacher, F. R. and Krein, M. G., Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems, Revised Edition. American Mathematical Society, 2002. Template:Isbn