compound matrix
   HOME

TheInfoList



OR:

In
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices ...
, 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 algebra In mathematics, the exterior algebra, or Grassmann algebra, named after Hermann Grassmann, is an algebra that uses the exterior product or wedge product as its multiplication. In mathematics, the exterior product or wedge product of vectors is a ...
s, 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 be an matrix with
real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...
or
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
entries. If is a subset of size of and is a subset of size of , then the -submatrix of , written  , is the submatrix formed from by retaining only those rows indexed by and those columns indexed by . If , then is the - minor of . The ''r'' th compound matrix of is a matrix, denoted , is defined as follows. If , then is the unique matrix. Otherwise, has size \binom \!\times\! \binom. Its rows and columns are indexed by -element subsets of and , respectively, in their
lexicographic order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
. The entry corresponding to subsets and is the minor . 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 = \begin 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end. The rows are indexed by and the columns by . Therefore, the rows of are indexed by the sets :\ < \ < \ and the columns are indexed by :\ < \ < \ < \ < \ < \. Using absolute value bars to denote
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...
s, the second compound matrix is :\begin C_2(A) &= \begin \left, \begin 1 & 2 \\ 5 & 6 \end\ & \left, \begin 1 & 3 \\ 5 & 7 \end\ & \left, \begin 1 & 4 \\ 5 & 8 \end\ & \left, \begin 2 & 3 \\ 6 & 7 \end\ & \left, \begin 2 & 4 \\ 6 & 8 \end\ & \left, \begin 3 & 4 \\ 7 & 8 \end\ \\ \left, \begin 1 & 2 \\ 9 & 10 \end\ & \left, \begin 1 & 3 \\ 9 & 11 \end\ & \left, \begin 1 & 4 \\ 9 & 12 \end\ & \left, \begin 2 & 3 \\ 10 & 11 \end\ & \left, \begin 2 & 4 \\ 10 & 12 \end\ & \left, \begin 3 & 4 \\ 11 & 12 \end\ \\ \left, \begin 5 & 6 \\ 9 & 10 \end\ & \left, \begin 5 & 7 \\ 9 & 11 \end\ & \left, \begin 5 & 8 \\ 9 & 12 \end\ & \left, \begin 6 & 7 \\ 10 & 11 \end\ & \left, \begin 6 & 8 \\ 10 & 12 \end\ & \left, \begin 7 & 8 \\ 11 & 12 \end\ \end \\ &= \begin -4 & -8 & -12 & -4 & -8 & -4 \\ -8 & -16 & -24 & -8 & -16 & -8 \\ -4 & -8 & -12 & -4 & -8 & -4 \end. \end


Properties

Let be a scalar, be an matrix, and be an matrix. For a positive
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
, let denote the identity matrix. The
transpose In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations). The tr ...
of a matrix will be written , and the
conjugate transpose In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \boldsymbol is an n \times m matrix obtained by transposing \boldsymbol and applying complex conjugate on each entry (the complex c ...
by . Then: * , a identity matrix. * . * . * If , then . * If , then C_r(I_n) = I_. * If , then . * If , then . * , which is closely related to
Cauchy–Binet formula In mathematics, specifically linear algebra, the Cauchy–Binet formula, named after Augustin-Louis Cauchy and Jacques Philippe Marie Binet, is an identity for the determinant of the product of two rectangular matrices of transpose shapes (so tha ...
. Assume in addition that is a square matrix of size . Then: * . * If has one of the following properties, then so does : **
Upper triangular In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal ar ...
, **
Lower triangular In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
, **
Diagonal In geometry, a diagonal is a line segment joining two vertices of a polygon or polyhedron, when those vertices are not on the same edge. Informally, any sloping line is called diagonal. The word ''diagonal'' derives from the ancient Greek δ ...
, ** Orthogonal, **
Unitary Unitary may refer to: Mathematics * Unitary divisor * Unitary element * Unitary group * Unitary matrix * Unitary morphism * Unitary operator * Unitary transformation * Unitary representation * Unitarity (physics) * ''E''-unitary inverse semigrou ...
, **
Symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
, **
Hermitian {{Short description, none Numerous things are named after the French mathematician Charles Hermite (1822–1901): Hermite * Cubic Hermite spline, a type of third-degree spline * Gauss–Hermite quadrature, an extension of Gaussian quadrature m ...
, ** Skew-symmetric, **
Skew-hermitian __NOTOC__ In linear algebra, a square matrix with Complex number, complex entries is said to be skew-Hermitian or anti-Hermitian if its conjugate transpose is the negative of the original matrix. That is, the matrix A is skew-Hermitian if it satisf ...
, ** Positive definite, ** Positive semi-definite, **
Normal Normal(s) or The Normal(s) may refer to: Film and television * ''Normal'' (2003 film), starring Jessica Lange and Tom Wilkinson * ''Normal'' (2007 film), starring Carrie-Anne Moss, Kevin Zegers, Callum Keith Rennie, and Andrew Airlie * ''Norma ...
. * If is
invertible In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers. Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
, then so is , and . * (Sylvester–Franke theorem) If , then \det C_r(A) = (\det A)^.


Relation to exterior powers

Give the standard coordinate basis . The  th exterior power of is the
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
:\wedge^r \mathbf^n whose
basis Basis may refer to: Finance and accounting * Adjusted basis, the net cost of an asset after adjusting for various tax-related items *Basis point, 0.01%, often used in the context of interest rates * Basis trading, a trading strategy consisting ...
consists of the formal symbols :\mathbf_ \wedge \dots \wedge \mathbf_, where :i_1 < \dots < i_r. Suppose that is an matrix. Then corresponds to a
linear transformation In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pre ...
:A \colon \mathbf^n \to \mathbf^m. Taking the  th exterior power of this linear transformation determines a linear transformation :\wedge^r A \colon \wedge^r \mathbf^n \to \wedge^r \mathbf^m. The matrix corresponding to this linear transformation (with respect to the above bases of the exterior powers) is . Taking exterior powers is a
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
, which means that :\wedge^r (AB) = (\wedge^r A)(\wedge^r B). This corresponds to the formula . It is closely related to, and is a strengthening of, the
Cauchy–Binet formula In mathematics, specifically linear algebra, the Cauchy–Binet formula, named after Augustin-Louis Cauchy and Jacques Philippe Marie Binet, is an identity for the determinant of the product of two rectangular matrices of transpose shapes (so tha ...
.


Relation to adjugate matrices

Let be an matrix. Recall that its  th higher adjugate matrix is the \binom \!\times\! \binom matrix whose entry is :(-1)^ \det A_, where, for any set of integers, is the sum of the elements of . The adjugate of is its 1st higher adjugate and is denoted . The generalized
Laplace expansion In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression of the determinant of an matrix as a weighted sum of minors, which are the determinants of some submatrices of . Spec ...
formula implies :C_r(A)\operatorname_r(A) = \operatorname_r(A)C_r(A) = (\det A)I_. If is invertible, then :\operatorname_r(A^) = (\det A)^C_r(A). A concrete consequence of this is Jacobi's formula for the minors of an
inverse matrix In linear algebra, an -by- square matrix is called invertible (also nonsingular or nondegenerate), if there exists an -by- square matrix such that :\mathbf = \mathbf = \mathbf_n \ where denotes the -by- identity matrix and the multiplicati ...
: :\det(A^)_ = (-1)^ \frac. Adjugates can also be expressed in terms of compounds. Let denote the ''sign matrix'': :S = \operatorname(1, -1, 1, -1, \ldots, (-1)^), and let denote the ''
exchange matrix In mathematics, especially linear algebra, the exchange matrices (also called the reversal matrix, backward identity, or standard involutory permutation) are special cases of permutation matrices, where the 1 elements reside on the antidiagonal and ...
'': :J = \begin & & 1 \\ & \cdots & \\ 1 & & \end. Then Jacobi's theorem states that the  th higher adjugate matrix is: :\operatorname_r(A) = JC_(SAS)^TJ. It follows immediately from Jacobi's theorem that :C_r(A)\, J(C_(SAS))^TJ = (\det A)I_. 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(\operatorname_s(A)) = (\det A)^rI, :C_r(C_s(A))\operatorname_r(C_s(A)) = (\det C_s(A))I, and the Sylvester-Franke theorem, we deduce :\operatorname_r(C_s(A)) = (\det A)^ C_r(\operatorname_s(A)). The same technique leads to an additional identity, :\operatorname(C_r(A)) = (\det A)^ C_r(\operatorname(A)). Compound and adjugate matrices appear when computing determinants of linear combinations of matrices. It is elementary to check that if and are matrices then :\det(sA + tB) = C_n\!\left(\begin sA & I_n \end\right)C_n\!\left(\begin I_n \\ tB \end\right). It is also true that: :\det(sA + tB) = \sum_^n s^r t^ \operatorname(\operatorname_r(A)C_r(B)). This has the immediate consequence :\det(I + A) = \sum_^n \operatorname \operatorname_r(A) = \sum_^n \operatorname 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.


Notes


Citations


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 Matrices