Editing Minor (linear algebra)

{{Short description|Determinant of a subsection of a square matrix}}
{{About|a concept in linear algebra|the concept of "minor" in graph theory|Graph minor}}

In [[linear algebra]], a '''minor''' of a [[matrix (mathematics)|matrix]] {{math|'''A'''}} is the [[determinant]] of some smaller [[square matrix]] generated from {{math|'''A'''}} by removing one or more of its rows and columns. Minors obtained by removing just one row and one column from square matrices ('''first minors''') are required for calculating matrix '''cofactors''', which are useful for computing both the determinant and [[Inverse matrix|inverse]] of square matrices.  The requirement that the square matrix be smaller than the original matrix is often omitted in the definition.

==Definition and illustration==

===First minors===

If {{math|'''A'''}} is a square matrix, then the ''minor'' of the entry in the {{mvar|i}}-th row and {{mvar|j}}-th column (also called the {{math|(''i'', ''j'')}} ''minor'', or a ''first minor''<ref>Burnside, William Snow & Panton, Arthur William (1886) ''[https://books.google.com/books?id=BhgPAAAAIAAJ&pg=PA239 Theory of Equations: with an Introduction to the Theory of Binary Algebraic Form]''.</ref>) is the [[determinant]] of the [[submatrix]] formed by deleting the {{mvar|i}}-th row and {{mvar|j}}-th column. This number is often denoted {{math|''M''<sub>''i'', ''j''</sub>}}. The {{math|(''i'', ''j'')}} ''cofactor'' is obtained by multiplying the minor by {{math|(&minus;1){{sup|''i'' + ''j''}}}}.

To illustrate these definitions, consider the following {{nowrap|3&thinsp;×&thinsp;3}} matrix,

<math display=block>\begin{bmatrix}
1 & 4 & 7 \\
3 & 0 & 5 \\
-1 & 9 & 11 \\
\end{bmatrix}</math>

To compute the minor {{math|''M''<sub>2,3</sub>}} and the cofactor {{math|''C''<sub>2,3</sub>}}, we find the determinant of the above matrix with row 2 and column 3 removed.

<math display=block> M_{2,3} = \det \begin{bmatrix}
  1    & 4    & \Box \\
  \Box & \Box & \Box \\
  -1   & 9    & \Box \\
\end{bmatrix}= \det \begin{bmatrix}
  1 & 4 \\
  -1 & 9 \\
\end{bmatrix} = 9-(-4) = 13</math>

So the cofactor of the {{nowrap|(2,3)}} entry is

<math display=block>C_{2,3} = (-1)^{2+3}(M_{2,3}) = -13.</math>

===General definition===

Let {{math|'''A'''}} be an {{math|''m'' × ''n''}} matrix and {{mvar|k}} an [[integer]] with {{math|0 < ''k'' ≤ ''m''}}, and {{math|''k'' ≤ ''n''}}. A {{math|''k'' × ''k''}} ''minor'' of {{math|'''A'''}}, also called ''minor determinant of order {{mvar|k}}'' of {{math|'''A'''}} or, if {{math|''m'' {{=}} ''n''}}, the {{math|(''n'' − ''k'')}}''th'' ''minor determinant'' of {{math|'''A'''}} (the word "determinant" is often omitted, and the word "degree" is sometimes used instead of "order") is the determinant of a {{math|''k'' × ''k''}} matrix obtained from {{math|'''A'''}} by deleting {{math|''m'' − ''k''}} rows and {{math|''n'' − ''k''}} columns. Sometimes the term is used to refer to the {{math|''k'' × ''k''}} matrix obtained from {{math|'''A'''}} as above (by deleting {{math|''m'' − ''k''}} rows and {{math|''n'' − ''k''}} columns), but this matrix should be referred to as a ''(square) submatrix'' of {{math|'''A'''}}, leaving the term "minor" to refer to the determinant of this matrix. For a matrix {{math|'''A'''}} as above, there are a total of <math display="inline">{m \choose k} \cdot {n \choose k}</math> minors of size {{math|''k'' × ''k''}}. The ''minor of order zero'' is often defined to be 1. For a square matrix, the ''zeroth minor'' is just the determinant of the matrix.<ref name="Hohn">Elementary Matrix Algebra (Third edition), Franz E. Hohn, The Macmillan Company, 1973, {{isbn|978-0-02-355950-1}}</ref><ref name="Encyclopedia of Mathematics" />

Let 
<math display=block>\begin{align}
  I &= 1 \le i_1 < i_2 < \cdots < i_k \le m, \\[2pt]
  J &= 1 \le j_1 < j_2 < \cdots < j_k \le n,
\end{align}</math>
be ordered sequences (in natural order, as it is always assumed when talking about minors unless otherwise stated) of indexes. The minor <math display="inline">\det \bigl( (\mathbf A_{i_p, j_q})_{p,q = 1, \ldots, k} \bigr)</math> corresponding to these choices of indexes is denoted <math>\det_{I,J} A</math> or <math>\det \mathbf A_{I, J}</math> or <math>[\mathbf A]_{I,J}</math> or <math>M_{I,J}</math> or <math>M_{i_1, i_2, \ldots, i_k, j_1, j_2, \ldots, j_k}</math> or <math>M_{(i),(j)}</math> (where the {{math|(''i'')}} denotes the sequence of indexes {{mvar|I}}, etc.), depending on the source. Also, there are two types of denotations in use in literature: by the minor associated to ordered sequences of indexes {{mvar|I}} and {{mvar|J}}, some authors<ref>Linear Algebra and Geometry, Igor R. Shafarevich,  Alexey O. Remizov, Springer-Verlag Berlin Heidelberg, 2013, {{isbn|978-3-642-30993-9}}</ref> mean the determinant of the matrix that is formed as above, by taking the elements of the original matrix from the rows whose indexes are in {{mvar|I}} and columns whose indexes are in {{mvar|J}}, whereas some other authors mean by a minor associated to {{mvar|I}} and {{mvar|J}} the determinant of the matrix formed from the original matrix by deleting the rows in {{mvar|I}} and columns in {{mvar|J}};<ref name="Hohn" /> which notation is used should always be checked. In this article, we use the inclusive definition of choosing the elements from rows of {{mvar|I}} and columns of {{mvar|J}}. The exceptional case is the case of the first minor or the {{math|(''i'', ''j'')}}-minor described above; in that case, the exclusive meaning <math display="inline">M_{i,j} = \det \bigl( \left( \mathbf A_{p,q} \right)_{p \neq i, q \neq j} \bigr)</math> is standard everywhere in the literature and is used in this article also.

===Complement===

The complement {{math|''B''<sub>''ijk''..., ''pqr''...</sub>}} of a minor {{math|''M''<sub>''ijk''..., ''pqr''...</sub>}} of a square matrix, {{math|'''A'''}}, is formed by the determinant of the matrix {{math|'''A'''}} from which all the rows ({{mvar|ijk...}}) and columns ({{mvar|pqr...}}) associated with {{math|''M''<sub>''ijk''..., ''pqr''...</sub>}} have been removed.  The complement of the first minor of an element {{mvar|a<sub>ij</sub>}} is merely that element.<ref>Bertha Jeffreys, [https://books.google.com/books?id=Qs-xdYBQ_5wC&pg=PA135 ''Methods of Mathematical Physics''], p.135, Cambridge University Press, 1999 {{isbn|0-521-66402-0}}.</ref>

==Applications of minors and cofactors==

===Cofactor expansion of the determinant===
{{main|Laplace expansion}}

The cofactors feature prominently in [[Laplace expansion|Laplace's formula]] for the expansion of determinants, which is a method of computing larger determinants in terms of smaller ones. Given an {{math|''n'' × ''n''}} matrix {{math|1='''A''' = (''a{{sub|ij}}'')}}, the determinant of {{math|'''A'''}}, denoted {{math|det('''A''')}}, can be written as the sum of the cofactors of any row or column of the matrix multiplied by the entries that generated them. In other words, defining <math>C_{ij} = (-1)^{i+j} M_{ij}</math> then the cofactor expansion along the {{mvar|j}}-th column gives:

<math display=block>\begin{align}
  \det(\mathbf A) &= a_{1j}C_{1j} + a_{2j}C_{2j} + a_{3j}C_{3j} + \cdots + a_{nj}C_{nj} \\[2pt]
  &= \sum_{i=1}^{n} a_{ij} C_{ij} \\[2pt]
  &= \sum_{i=1}^{n} a_{ij}(-1)^{i+j} M_{ij}
\end{align}</math>

The cofactor expansion along the {{mvar|i}}-th row gives:

<math display=block>\begin{align}
  \det(\mathbf A) &= a_{i1}C_{i1} + a_{i2}C_{i2} + a_{i3}C_{i3} + \cdots + a_{in}C_{in} \\[2pt]
  &= \sum_{j=1}^{n} a_{ij} C_{ij} \\[2pt]
  &= \sum_{j=1}^{n} a_{ij} (-1)^{i+j} M_{ij}
\end{align}</math>

===Inverse of a matrix===
{{main|Invertible matrix}}

One can write down the inverse of an [[invertible matrix]] by computing its cofactors by using [[Cramer's rule]], as follows. The matrix formed by all of the cofactors of a square matrix {{math|'''A'''}} is called the '''cofactor matrix''' (also called the '''matrix of cofactors''' or, sometimes, ''comatrix''):

<math display=block>\mathbf C = \begin{bmatrix}
  C_{11}  & C_{12} & \cdots &   C_{1n} \\
  C_{21}  & C_{22} & \cdots &   C_{2n} \\
   \vdots & \vdots & \ddots & \vdots \\
  C_{n1}  & C_{n2} & \cdots &  C_{nn}
\end{bmatrix} </math>

Then the inverse of {{math|'''A'''}} is the transpose of the cofactor matrix times the reciprocal of the determinant of {{math|'''A'''}}:

<math display=block>\mathbf A^{-1} = \frac{1}{\operatorname{det}(\mathbf A)} \mathbf C^\mathsf{T}.</math>

The transpose of the cofactor matrix is called the [[adjugate]] matrix (also called the ''classical adjoint'') of {{math|'''A'''}}.

The above formula can be generalized as follows: Let 
<math display=block>\begin{align}
  I &= 1 \le i_1 < i_2 < \ldots < i_k \le n, \\[2pt]
  J &= 1 \le j_1 < j_2 < \ldots < j_k \le n,
\end{align}</math>
be ordered sequences (in natural order) of indexes (here {{math|'''A'''}} is an {{math|''n'' × ''n''}} matrix). Then<ref name="Prasolov1994">{{cite book|author=Viktor Vasil_evich Prasolov|title=Problems and Theorems in Linear Algebra|url=https://books.google.com/books?id=b4yKAwAAQBAJ&pg=PR15|date=13 June 1994|publisher=American Mathematical Soc.|isbn=978-0-8218-0236-6|pages=15–}}</ref>

<math display=block>[\mathbf A^{-1}]_{I,J} = \pm\frac{[\mathbf A]_{J',I'}}{\det \mathbf A},</math>

where {{math|''I′'', ''J′''}} denote the ordered sequences of indices (the indices are in natural order of magnitude, as above) complementary to {{math|''I'', ''J''}}, so that every index {{math|1, ..., ''n''}} appears exactly once in either {{mvar|I}} or {{mvar|I'}}, but not in both (similarly for the  {{mvar|J}} and {{mvar|J'}}) and {{math|['''A''']<sub>''I'', ''J''</sub>}} denotes the determinant of the submatrix of {{math|'''A'''}} formed by choosing the rows of the index set {{mvar|I}} and columns of index set {{mvar|J}}. Also, <math>[\mathbf A]_{I,J} = \det \bigl( (A_{i_p, j_q})_{p,q = 1, \ldots, k} \bigr).</math> A simple proof can be given using wedge product. Indeed,

<math display=block>\bigl[ \mathbf A^{-1} \bigr]_{I,J} (e_1\wedge\ldots \wedge e_n) = \pm(\mathbf A^{-1}e_{j_1})\wedge \ldots \wedge(\mathbf A^{-1}e_{j_k})\wedge e_{i'_1}\wedge\ldots \wedge e_{i'_{n-k}}, </math>

where <math>e_1, \ldots, e_n</math> are the basis vectors. Acting by {{math|'''A'''}} on both sides, one gets

<math display=block>\begin{align}
  &\ \bigl[\mathbf A^{-1} \bigr]_{I,J} \det \mathbf A (e_1\wedge\ldots \wedge e_n) \\[2pt]
  =&\ \pm (e_{j_1})\wedge \ldots \wedge(e_{j_k})\wedge (\mathbf A e_{i'_1})\wedge\ldots \wedge (\mathbf A e_{i'_{n-k}}) \\[2pt]
  =&\ \pm [\mathbf A]_{J',I'}(e_1\wedge\ldots \wedge e_n).
\end{align}</math>

The sign can be worked out to be 
<math display=block>(-1)^\wedge \!\!\left( \sum_{s=1}^{k} i_s - \sum_{s=1}^{k} j_s \right),</math>
so the sign is determined by the sums of elements in {{mvar|I}} and {{mvar|J}}.

===Other applications===
Given an {{math|''m'' × ''n''}} matrix with [[real number|real]] entries (or entries from any other [[field (mathematics)|field]]) and [[rank (matrix theory)|rank]] {{mvar|r}}, then there exists at least one non-zero {{math|''r'' × ''r''}} minor, while all larger minors are zero.

We will use the following notation for minors: if {{math|'''A'''}} is an {{math|''m'' × ''n''}} matrix, {{mvar|I}} is a [[subset]] of {{math|{1, ..., ''m''} }} with {{mvar|k}} elements, and {{mvar|J}} is a subset of {{math|{1, ..., ''n''} }} with {{mvar|k}} elements, then we write {{math|['''A''']<sub>''I'', ''J''</sub>}} for the {{math|''k'' × ''k''}} minor of {{math|'''A'''}} that corresponds to the rows with index in {{mvar|I}} and the columns with index in {{mvar|J}}.
* If {{math|1=''I'' = ''J''}}, then {{math|['''A''']<sub>''I'', ''J''</sub>}} is called a ''principal minor''.
* If the matrix that corresponds to a principal minor is a square upper-left [[Matrix (mathematics)#Submatrix|submatrix]] of the larger matrix (i.e., it consists of matrix elements in rows and columns from 1 to {{mvar|k}}, also known as a leading principal submatrix), then the principal minor is called a ''leading principal minor (of order {{mvar|k}})'' or ''corner (principal) minor (of order {{mvar|k}})''.<ref name="Encyclopedia of Mathematics">{{cite book |chapter=Minor |title=Encyclopedia of Mathematics |url=http://www.encyclopediaofmath.org/index.php?title=Minor&oldid=30176 }}</ref> For an {{math|''n'' × ''n''}} square matrix, there are {{mvar|n}} leading principal minors.
* A ''basic minor'' of a matrix is the determinant of a square submatrix that is of maximal size with nonzero determinant.<ref name="Encyclopedia of Mathematics" />
* For [[Hermitian matrix|Hermitian matrices]], the leading principal minors can be used to test for [[positive-definite matrix|positive definiteness]] and the principal minors can be used to test for [[positive-semidefinite matrix|positive semidefiniteness]]. See [[Sylvester's criterion]] for more details.

Both the formula for ordinary [[matrix multiplication]] and the [[Cauchy–Binet formula]] for the determinant of the product of two matrices are special cases of the following general statement about the minors of a product of two matrices.
Suppose that {{math|'''A'''}} is an {{math|''m'' × ''n''}} matrix, {{math|'''B'''}} is an {{math|''n'' × ''p''}} matrix, {{mvar|I}} is a [[subset]] of {{math|{1, ..., ''m''} }} with {{mvar|k}} elements and {{mvar|J}} is a subset of {{math|{1, ..., ''p''} }} with {{mvar|k}} elements. Then
<math display=block>[\mathbf{AB}]_{I,J} = \sum_{K} [\mathbf{A}]_{I,K} [\mathbf{B}]_{K,J}\,</math>
where the sum extends over all subsets {{mvar|K}} of {{math|{1, ..., ''n''} }} with {{mvar|k}} elements. This formula is a straightforward extension of the Cauchy–Binet formula.

==Multilinear algebra approach==

A more systematic, algebraic treatment of minors is given in [[multilinear algebra]], using the [[wedge product]]: the {{mvar|k}}-minors of a matrix are the entries in the {{mvar|k}}-th [[exterior power]] map.

If the columns of a matrix are wedged together {{mvar|k}} at a time, the {{math|''k'' × ''k''}} minors appear as the components of the resulting {{mvar|k}}-vectors. For example, the 2&thinsp;×&thinsp;2 minors of the matrix
<math display=block>\begin{pmatrix}
  1 & 4 \\
  3 & \!\!-1 \\
  2 & 1 \\
\end{pmatrix}</math>
are −13 (from the first two rows), −7 (from the first and last row), and 5 (from the last two rows). Now consider the wedge product
<math display=block>(\mathbf{e}_1 + 3\mathbf{e}_2 + 2\mathbf{e}_3) \wedge (4\mathbf{e}_1 - \mathbf{e}_2 + \mathbf{e}_3)</math>
where the two expressions correspond to the two columns of our matrix. Using the properties of the wedge product, namely that it is [[bilinear map|bilinear]] and [[alternating multilinear map|alternating]],
<math display=block>\mathbf{e}_i \wedge \mathbf{e}_i = 0,</math>
and [[anticommutativity|antisymmetric]],
<math display=block>\mathbf{e}_i\wedge \mathbf{e}_j = - \mathbf{e}_j\wedge \mathbf{e}_i,</math>
we can simplify this expression to
<math display=block> -13 \mathbf{e}_1\wedge \mathbf{e}_2 -7 \mathbf{e}_1\wedge \mathbf{e}_3 +5 \mathbf{e}_2\wedge \mathbf{e}_3</math>
where the coefficients agree with the minors computed earlier.

==A remark about different notation==
In some books, instead of ''cofactor'' the term ''adjunct'' is used.<ref>[[Felix Gantmacher]], ''Theory of matrices'' (1st ed., original language is Russian), Moscow: State Publishing House of technical and theoretical literature, 1953, p.491,</ref> Moreover, it is denoted as {{math|'''A'''<sub>''ij''</sub>}} and defined in the same way as cofactor:
<math display=block>\mathbf{A}_{ij} = (-1)^{i+j} \mathbf{M}_{ij}</math>

Using this notation the inverse matrix is written this way:
<math display=block>\mathbf{M}^{-1} = \frac{1}{\det(M)}\begin{bmatrix}
  A_{11}  & A_{21} & \cdots &   A_{n1}   \\
  A_{12}  & A_{22} & \cdots &   A_{n2}   \\
   \vdots & \vdots & \ddots & \vdots \\
  A_{1n}  & A_{2n} & \cdots &  A_{nn}
\end{bmatrix} </math>

Keep in mind that ''adjunct'' is not [[adjugate]] or [[adjoint]]. In modern terminology, the "adjoint" of a matrix most often refers to the corresponding  [[adjoint operator]].

==See also==
* [[Submatrix]]
* [[Compound matrix]]

==References==
{{reflist}}

==External links==
* [http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/lecture-19-determinant-formulas-and-cofactors/ MIT Linear Algebra Lecture on Cofactors] at Google Video, from MIT OpenCourseWare
* [http://planetmath.org/encyclopedia/Cofactor.html PlanetMath entry of ''Cofactors'']
* [http://www.encyclopediaofmath.org/index.php/Minor Springer Encyclopedia of Mathematics entry for ''Minor'']

{{linear algebra}}

[[Category:Matrix theory]]
[[Category:Determinants]]