Compound matrix

From HandWiki
Short description: Matrix whose entries are all minors of another matrix

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.[1][2][3][4] Compound matrices are closely related to exterior algebras,[5] 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.[4][6]

Definition

Let A be an m × n matrix with real or complex entries.[lower-alpha 1] If I is a subset of size r of {1, ..., m} and J is a subset of size s of {1, ..., n}, then the (I, J )-submatrix of A, written AI, J , is the submatrix formed from A by retaining only those rows indexed by I and those columns indexed by J. If r = s, then det AI, J is the (I, J )-minor of A.

The r th compound matrix of A is a matrix, denoted Cr(A), is defined as follows. If r > min(m, n), then Cr(A) is the unique 0 × 0 matrix. Otherwise, Cr(A) has size [math]\displaystyle{ \binom{m}{r} \!\times\! \binom{n}{r} }[/math]. Its rows and columns are indexed by r-element subsets of {1, ..., m} and {1, ..., n}, respectively, in their lexicographic order. The entry corresponding to subsets I and J is the minor det AI, J.

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.[7]

For example, consider the matrix

[math]\displaystyle{ A = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{pmatrix}. }[/math]

The rows are indexed by {1, 2, 3} and the columns by {1, 2, 3, 4}. Therefore, the rows of C2 (A) are indexed by the sets

[math]\displaystyle{ \{1, 2\} \lt \{1, 3\} \lt \{2, 3\} }[/math]

and the columns are indexed by

[math]\displaystyle{ \{1, 2\} \lt \{1, 3\} \lt \{1, 4\} \lt \{2, 3\} \lt \{2, 4\} \lt \{3, 4\}. }[/math]

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

[math]\displaystyle{ \begin{align} C_2(A) &= \begin{pmatrix} \left|\begin{smallmatrix} 1 & 2 \\ 5 & 6 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 1 & 3 \\ 5 & 7 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 1 & 4 \\ 5 & 8 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 2 & 3 \\ 6 & 7 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 2 & 4 \\ 6 & 8 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 3 & 4 \\ 7 & 8 \end{smallmatrix}\right| \\ \left|\begin{smallmatrix} 1 & 2 \\ 9 & 10 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 1 & 3 \\ 9 & 11 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 1 & 4 \\ 9 & 12 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 2 & 3 \\ 10 & 11 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 2 & 4 \\ 10 & 12 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 3 & 4 \\ 11 & 12 \end{smallmatrix}\right| \\ \left|\begin{smallmatrix} 5 & 6 \\ 9 & 10 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 5 & 7 \\ 9 & 11 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 5 & 8 \\ 9 & 12 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 6 & 7 \\ 10 & 11 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 6 & 8 \\ 10 & 12 \end{smallmatrix}\right| & \left|\begin{smallmatrix} 7 & 8 \\ 11 & 12 \end{smallmatrix}\right| \end{pmatrix} \\ &= \begin{pmatrix} -4 & -8 & -12 & -4 & -8 & -4 \\ -8 & -16 & -24 & -8 & -16 & -8 \\ -4 & -8 & -12 & -4 & -8 & -4 \end{pmatrix}. \end{align} }[/math]

Properties

Let c be a scalar, A be an m × n matrix, and B be an n × p matrix. For k a positive integer, let Ik denote the k × k identity matrix. The transpose of a matrix M will be written MT, and the conjugate transpose by M*. Then:[8]

  • C0 (A) = I1, a 1 × 1 identity matrix.
  • C1(A) = A.
  • Cr(cA) = crCr(A).
  • If rk A = r, then rk Cr(A) = 1.
  • If 1 ≤ rn, then [math]\displaystyle{ C_r(I_n) = I_{\binom{n}{r}} }[/math].
  • If 1 ≤ r ≤ min(m, n), then Cr(AT) = Cr(A)T.
  • If 1 ≤ r ≤ min(m, n), then Cr(A*) = Cr(A)*.
  • Cr(AB) = Cr(A) Cr(B), which is closely related to Cauchy–Binet formula.

Assume in addition that A is a square matrix of size n. Then:[9]

  • Cn(A) = det A.
  • If A has one of the following properties, then so does Cr(A):
  • If A is invertible, then so is Cr(A), and Cr(A−1) = Cr(A)−1.
  • (Sylvester–Franke theorem) If 1 ≤ rn, then [math]\displaystyle{ \det C_r(A) = (\det A)^{\binom{n-1}{r-1}} }[/math].[10][11]

Relation to exterior powers

Give Rn the standard coordinate basis e1, ..., en. The r th exterior power of Rn is the vector space

[math]\displaystyle{ \wedge^r \mathbf{R}^n }[/math]

whose basis consists of the formal symbols

[math]\displaystyle{ \mathbf{e}_{i_1} \wedge \dots \wedge \mathbf{e}_{i_r}, }[/math]

where

[math]\displaystyle{ i_1 \lt \dots \lt i_r. }[/math]

Suppose that A is an m × n matrix. Then A corresponds to a linear transformation

[math]\displaystyle{ A \colon \mathbf{R}^n \to \mathbf{R}^m. }[/math]

Taking the r th exterior power of this linear transformation determines a linear transformation

[math]\displaystyle{ \wedge^r A \colon \wedge^r \mathbf{R}^n \to \wedge^r \mathbf{R}^m. }[/math]

The matrix corresponding to this linear transformation (with respect to the above bases of the exterior powers) is Cr(A). Taking exterior powers is a functor, which means that[12]

[math]\displaystyle{ \wedge^r (AB) = (\wedge^r A)(\wedge^r B). }[/math]

This corresponds to the formula Cr(AB) = Cr(A)Cr(B). It is closely related to, and is a strengthening of, the Cauchy–Binet formula.

Relation to adjugate matrices

Let A be an n × n matrix. Recall that its r th higher adjugate matrix adjr(A) is the [math]\displaystyle{ \binom{n}{r} \!\times\! \binom{n}{r} }[/math] matrix whose (I, J ) entry is

[math]\displaystyle{ (-1)^{\sigma(I) + \sigma(J)} \det A_{J^c, I^c}, }[/math]

where, for any set K of integers, σ(K) is the sum of the elements of K. The adjugate of A is its 1st higher adjugate and is denoted adj(A). The generalized Laplace expansion formula implies

[math]\displaystyle{ C_r(A)\operatorname{adj}_r(A) = \operatorname{adj}_r(A)C_r(A) = (\det A)I_{\binom{n}{r}}. }[/math]

If A is invertible, then

[math]\displaystyle{ \operatorname{adj}_r(A^{-1}) = (\det A)^{-1}C_r(A). }[/math]

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

[math]\displaystyle{ \det(A^{-1})_{J^c, I^c} = (-1)^{\sigma(I) + \sigma(J)} \frac{\det A_{I,J}}{\det A}. }[/math]

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

[math]\displaystyle{ S = \operatorname{diag}(1, -1, 1, -1, \ldots, (-1)^{n-1}), }[/math]

and let J denote the exchange matrix:

[math]\displaystyle{ J = \begin{pmatrix} & & 1 \\ & \cdots & \\ 1 & & \end{pmatrix}. }[/math]

Then Jacobi's theorem states that the r th higher adjugate matrix is:[13][14]

[math]\displaystyle{ \operatorname{adj}_r(A) = JC_{n-r}(SAS)^TJ. }[/math]

It follows immediately from Jacobi's theorem that

[math]\displaystyle{ C_r(A)\, J(C_{n-r}(SAS))^TJ = (\det A)I_{\binom{n}{r}}. }[/math]

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

[math]\displaystyle{ C_r(C_s(A))C_r(\operatorname{adj}_s(A)) = (\det A)^rI, }[/math]
[math]\displaystyle{ C_r(C_s(A))\operatorname{adj}_r(C_s(A)) = (\det C_s(A))I, }[/math]

and the Sylvester-Franke theorem, we deduce

[math]\displaystyle{ \operatorname{adj}_r(C_s(A)) = (\det A)^{\binom{n-1}{s-1}-r} C_r(\operatorname{adj}_s(A)). }[/math]

The same technique leads to an additional identity,

[math]\displaystyle{ \operatorname{adj}(C_r(A)) = (\det A)^{\binom{n-1}{r-1}-r} C_r(\operatorname{adj}(A)). }[/math]

Compound and adjugate matrices appear when computing determinants of linear combinations of matrices. It is elementary to check that if A and B are n × n matrices then

[math]\displaystyle{ \det(sA + tB) = C_n\!\left(\begin{bmatrix} sA & I_n \end{bmatrix}\right)C_n\!\left(\begin{bmatrix} I_n \\ tB \end{bmatrix}\right). }[/math]

It is also true that:[15][16]

[math]\displaystyle{ \det(sA + tB) = \sum_{r=0}^n s^r t^{n-r} \operatorname{tr}(\operatorname{adj}_r(A)C_r(B)). }[/math]

This has the immediate consequence

[math]\displaystyle{ \det(I + A) = \sum_{r=0}^n \operatorname{tr} \operatorname{adj}_r(A) = \sum_{r=0}^n \operatorname{tr} C_r(A). }[/math]

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.[17]

Notes

  1. The definition, and the purely algebraic part of the theory, of compound matrices requires only that the matrix have entries in a commutative ring. In this case, the matrix corresponds to a homomorphism of finitely generated free modules.

Citations

  1. DeAlba, Luz M. Determinants and Eigenvalues in Hogben, Leslie (ed) Handbook of Linear Algebra, 2nd edition, CRC Press, 2013, ISBN 978-1-4665-0729-6, p. 4-4
  2. Gantmacher, F. R., The Theory of Matrices, volume I, Chelsea Publishing Company, 1959, ISBN 978-0-8218-1376-8p. 20
  3. Horn, Roger A. and Johnson, Charles R., Matrix Analysis, 2nd edition, Cambridge University Press, 2013, ISBN 978-0-521-54823-6, p. 21
  4. 4.0 4.1 Muldowney, James S. (1990). "Compound matrices and ordinary differential equations" (in en). Rocky Mountain Journal of Mathematics 20 (4): 857–872. doi:10.1216/rmjm/1181073047. ISSN 0035-7596. http://projecteuclid.org/euclid.rmjm/1181073047. 
  5. Template:Cite tech report
  6. Bar-Shalom, Eyal; Dalin, Omri; Margaliot, Michael (2023-03-15). "Compound matrices in systems and control theory: a tutorial" (in en). Mathematics of Control, Signals, and Systems 35 (3): 467–521. doi:10.1007/s00498-023-00351-8. ISSN 0932-4194. https://link.springer.com/10.1007/s00498-023-00351-8. 
  7. Kung, Rota, and Yan, p. 305.
  8. Horn and Johnson, p. 22.
  9. Horn and Johnson, pp. 22, 93, 147, 233.
  10. Tornheim, Leonard (1952). "The Sylvester–Franke Theorem". The American Mathematical Monthly 59 (6): 389–391. doi:10.2307/2306811. ISSN 0002-9890. 
  11. Harley Flanders (1953) "A Note on the Sylvester-Franke Theorem", American Mathematical Monthly 60: 543–5, MR0057835
  12. Joseph P.S. Kung, Gian-Carlo Rota, and Catherine H. Yan, The Rota Way, Cambridge University Press, 2009, p. 306. ISBN 9780521883894
  13. Nambiar, K.K.; Sreevalsan, S. (2001). "Compound matrices and three celebrated theorems". Mathematical and Computer Modelling 34 (3–4): 251–255. doi:10.1016/S0895-7177(01)00058-9. ISSN 0895-7177. 
  14. Price, G. B. (1947). "Some Identities in the Theory of Determinants". The American Mathematical Monthly 54 (2): 75–90. doi:10.2307/2304856. ISSN 0002-9890. 
  15. Prells, Uwe; Friswell, Michael I.; Garvey, Seamus D. (2003-02-08). "Use of geometric algebra: compound matrices and the determinant of the sum of two matrices" (in en). Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 459 (2030): 273–285. doi:10.1098/rspa.2002.1040. ISSN 1364-5021. http://rspa.royalsocietypublishing.org/content/459/2030/273. 
  16. Horn and Johnson, p. 29
  17. Kravvaritis, Christos; Mitrouli, Marilena (2009-02-01). "Compound matrices: properties, numerical issues and analytical computations" (in en). Numerical Algorithms 50 (2): 155. doi:10.1007/s11075-008-9222-7. ISSN 1017-1398. http://users.uoa.gr/~mmitroul/mmitroulweb/numalg09.pdf. 

References

  • Gantmacher, F. R. and Krein, M. G., Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems, Revised Edition. American Mathematical Society, 2002. ISBN 978-0-8218-3171-7