The Laplace Theorem for Determinant

    27 Aug, 2024

    Laplace's theorem in determinants and its applications

    Definition (kk-th Order Minor): In an nn-th order determinant DD, a kk-th order minor MM is a k×kk \times k determinant formed by selecting any kk rows and kk columns from DD (knk \le n), and taking the k2k^2 elements at the intersections of these rows and columns in their original order.

    When k<nk < n, after removing these kk rows and kk columns from DD, the remaining (nk)(n-k)-th order determinant MM' formed by the leftover elements is called the cofactor of the kk-th order minor MM.

    Example:

    D=a11a12a13a14a15a21a22a23a24a25a51a52a53a54a55,M=a12a13a15a22a23a25a42a43a45,M=a31a34a51a54D=\begin{vmatrix} a_{11} & a_{12} & a_{13} & a_{14} & a_{15}\\ a_{21} & a_{22} & a_{23} & a_{24} & a_{25}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ a_{51} & a_{52} & a_{53} & a_{54} & a_{55} \end{vmatrix}, \\ M=\begin{vmatrix} a_{12} & a_{13} & a_{15} \\ a_{22} & a_{23} & a_{25} \\ a_{42} & a_{43} & a_{45} \end{vmatrix}, \\ M'=\begin{vmatrix} a_{31} & a_{34} \\ a_{51} & a_{54} \end{vmatrix}

    Note: In the above example, the algebraic cofactor of MM is

    (1)(1+2+4)+(2+3+5)M=M(-1)^{(1+2+4)+(2+3+5)}M'=-M'

    Definition (Algebraic Cofactor): Let MM be a kk-th order minor of DD with row and column indices i1,i2,,ik; j1,j2,,jki_{1},i_{2},\cdots,i_{k}; \ j_{1},j_{2},\cdots,j_{k}, respectively. The cofactor MM' of MM is multiplied by the sign (1)(i1+i2++ik)+(j1+j2++jk)(-1)^{(i_{1}+i_{2}+\cdots+i_{k})+(j_{1}+j_{2}+\cdots+j_{k})} to form the algebraic cofactor of MM.

    Lemma: Every term in the product of any minor MM of determinant DD and its algebraic cofactor AA corresponds to a term in the expansion of determinant DD, with the same sign.

    Proof: First, consider the case where MM is located in the upper-left corner of determinant DD:

    a11a12a1ka1,k+1a1nMak1ak2akkak,k+1aknak+1,1ak+1,2ak+1,kak+1,k+1ak+1,nMan1an2ankan,k+1ann\begin{vmatrix} a_{11} & a_{12} & \cdots & a_{1k} & |& a_{1,k+1} & \cdots & a_{1n}\\ \vdots & \vdots & M & \cdots & | & \vdots & &\vdots \\ a_{k1} & a_{k2} &\cdots & a_{kk}& | & a_{k,k+1} & \cdots & a_{kn}\\ -&- &- &- &-|-&- &- &- \\ a_{k+1,1}& a_{k+1,2} &\cdots & a_{k+1,k} & |& a_{k+1,k+1} & \cdots & a_{k+1,n}\\ \vdots & \vdots & & \vdots& |& \vdots & M' & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nk} & |& a_{n,k+1} & \cdots & a_{nn}\end{vmatrix}

    In this case, the algebraic cofactor of MM is:

    A=(1)(1+2++k)+(1+2++k)M=MA=(-1)^{(1+2+\cdots +k)+(1+2+\cdots+k)}M'=M'

    Each term in MM can be written as a1α1a2α2akαka_{1\alpha_{1}}a_{2\alpha_{2}}\cdots a_{k\alpha_{k}}, where α1α2αk\alpha_{1}\alpha_{2}\cdots\alpha_{k} is a permutation of 1,2,,k1,2,\cdots,k. The sign of this term is (1)τ(α1α2αk)(-1)^{\tau(\alpha_1 \alpha_2\cdots\alpha_k)}.

    Each term in MM' can be written as ak+1,βk+1ak+2,βk+2anβna_{k+1,\beta_{k+1}}a_{k+2,\beta_{k+2}}\cdots a_{n\beta_{n}}, where βk+1βk+2βn\beta_{k+1}\beta_{k+2}\cdots\beta_{n} is a permutation of k+1,k+2,,nk+1,k+2,\cdots,n, and its sign is (1)τ((βk+1k)(βk+2k)(βnk))(-1)^{\tau((\beta_{k+1}-k)(\beta_{k+2}-k)\cdots(\beta_{n}-k))}.

    The product of these two terms is a1α1a2α2akαkak+1,βk+1anβna_{1\alpha_{1}}a_{2\alpha_{2}}\cdots a_{k\alpha_{k}}a_{k+1,\beta_{k+1}}\cdots a_{n\beta_{n}}, and the combined sign is:

    (1)τ(α1α2αk)+τ((βk+1k)(βk+2k)(βnk))=(1)τ(α1α2αkβk+1βn)(-1)^{\tau(\alpha_{1}\alpha_{2}\cdots\alpha_{k})+\tau((\beta_{k+1}-k)(\beta_{k+2}-k)\cdots(\beta_{n}-k))}= (-1)^{\tau(\alpha_{1}\alpha_{2}\cdots \alpha_{k}\beta_{k+1}\cdots \beta_{n}) }

    Thus, this product is a term in the expansion of determinant DD with the same sign.

    Now, we will prove the general case.

    Let minor MM be located in rows i1,i2,,iki_1, i_2, \cdots, i_k and columns j1,j2,,jkj_1, j_2, \cdots, j_k of DD, where i1<i2<<iki_1 < i_2 < \cdots < i_k, and j1<j2<<jkj_1 < j_2 < \cdots < j_k.

    We rearrange the rows and columns of determinant DD such that MM is moved to the top-left corner.

    First, swap the i1i_1-th row with rows i11,i12,,2,1i_1-1, i_1-2, \cdots, 2, 1, which takes i11i_1-1 swaps to move the i1i_1-th row to the first row. Then, swap the i2i_2-th row i22i_2-2 times to move it to the second row, and so on. In total, this requires

    (i11)+(i22)++(ikk)=(i1+i2++ik)(1+2++k)(i_1-1)+(i_2-2)+\cdots+(i_k-k)=(i_1+i_2+\cdots+i_k)-(1+2+\cdots+k)

    row swaps to move rows i1,i2,,iki_1, i_2, \cdots, i_k to rows 1,2,,k1, 2, \cdots, k.

    Using similar column swaps, we move the columns of MM to columns 1,2,,k1, 2, \cdots, k, requiring

    (j11)+(j22)++(jkk)=(j1+j2++jk)(1+2++k)(j_1-1)+(j_2-2)+\cdots+(j_k-k)=(j_1+j_2+\cdots+j_k)-(1+2+\cdots+k)

    column swaps.

    Let D1D_1 denote the new determinant after these transformations. We have:

    D1=(1)(i1+i2++ik)(1+2++k)+(j1+j2++jk)(1+2++k)D=(1)i1+i2++ik+j1+j2++jkDD_1 = (-1)^{(i_1+i_2+\cdots+i_k)-(1+2+\cdots+k)+(j_1+j_2+\cdots+j_k)-(1+2+\cdots+k)}D \\ = (-1)^{i_1+i_2+\cdots+i_k+j_1+j_2+\cdots+j_k}D

    Thus, the expansion of D1D_1 contains the same terms as that of DD, but with each term having a sign difference of (1)i1+i2++ik+j1+j2++jk(-1)^{i_1+i_2+\cdots+i_k+j_1+j_2+\cdots+j_k}.

    Now, MM is located in the top-left corner of D1D_1, and the cofactor and algebraic cofactor of MM in D1D_1 are both MM'. Therefore, each term in the product MMMM' corresponds to a term in D1D_1 with the same sign.

    The algebraic cofactor AA of MM in DD gives MA=(1)i1+i2++ik+j1+j2++jkMMMA = (-1)^{i_1+i_2+\cdots+i_k+j_1+j_2+\cdots+j_k}MM', which is a term in D1D_1 with a sign difference of (1)i1+i2++ik+j1+j2++jk(-1)^{i_1+i_2+\cdots+i_k+j_1+j_2+\cdots+j_k}. Hence, MAMA is a term in DD with the same sign.

    Theorem (Laplace's Theorem): For any kk (1kn11 \le k \le n-1) rows chosen from determinant DD, the sum of the products of all kk-th order minors formed from these rows and their respective algebraic cofactors equals the determinant DD.

    Proof: Let the minors formed from the chosen kk rows of DD be M1,M2,,MtM_1, M_2, \cdots, M_t, with algebraic cofactors A1,A2,,AtA_1, A_2, \cdots, A_t. The theorem claims that:

    D=M1A1+M2A2++MtAtD = M_1A_1 + M_2A_2 + \cdots + M_tA_t

    where

    t=Cnk=n!k!(nk)!t = \text{C}_{n}^{k} = \dfrac{n!}{k!(n-k)!}

    By the lemma, each term in MiAiM_iA_i corresponds to a term in DD with the same sign, and there are no common terms between MiAiM_iA_i and MjAjM_jA_j (iji \ne j).

    The left-hand side of the equation contains n!n! terms, and the right-hand side contains

    i=1tk!(nk)!=k!(nk)!n!k!(nk)!=n!\sum\limits_{i=1}^{t}k!(n-k)! = k!(n-k)!\dfrac{n!}{k!(n-k)!} = n!

    terms. Hence, the theorem is proven.

    Example: In the determinant D=1214012110130131D=\begin{vmatrix} 1 & 2 & 1 &4 \\ 0 & -1 & 2 & 1\\ 1 & 0 & 1 & 3\\ 0 & 1& 3 & 1\end{vmatrix}, selecting the first two rows yields six minors:

    M1=1201=1,M2=1102=2,M3=1401=1,M_{1}= \begin{vmatrix} 1& 2\\ 0 &-1 \end{vmatrix}=-1, \quad M_{2}= \begin{vmatrix} 1 &1 \\ 0& 2\end{vmatrix}=2, \quad M_{3}= \begin{vmatrix} 1 & 4\\ 0 &1 \end{vmatrix}=1, M4=2112=5,M5=2411=6,M6=1421=7.M_{4}= \begin{vmatrix} 2& 1\\ -1&2 \end{vmatrix}=5, \quad M_{5}= \begin{vmatrix} 2& 4\\ -1 &1 \end{vmatrix}=6, \quad M_{6}= \begin{vmatrix} 1& 4\\ 2&1 \end{vmatrix}=-7.

    Their algebraic cofactors are:

    A1=8,A2=3,A3=1,A4=1,A5=3,A6=1D=7.A_1=-8, \quad A_2=3, \quad A_3=-1, \quad A_4=1, \quad A_5=-3, \quad A_6=1 \Rightarrow D=-7.

    Theorem: The product of two nn-order determinants

    D1=a11a12a1na21a22a2nan1an2ann,D2=b11b12b1nb21b22b2nbn1bn2bnnD_{1}=\begin{vmatrix} a_{11} & a_{12} & \cdots &a_{1n} \\ a_{21} &a_{22} &\cdots & a_{2n}\\ \vdots & \vdots & &\vdots \\ a_{n1} & a_{n2} &\cdots & a_{nn}\end{vmatrix}, \\ D_{2}=\begin{vmatrix} b_{11} & b_{12} & \cdots &b_{1n} \\ b_{21} &b_{22} &\cdots & b_{2n}\\ \vdots & \vdots & &\vdots \\ b_{n1} & b_{n2} &\cdots & b_{nn}\end{vmatrix}

    is equal to a determinant

    C=c11c12c1nc21c22c2ncn1cn2cnnC = \begin{vmatrix} c_{11} &c_{12} & \cdots &c_{1n} \\ c_{21} &c_{22} &\cdots & c_{2n}\\ \vdots & \vdots & &\vdots \\ c_{n1} & c_{n2} &\cdots & c_{nn}\end{vmatrix}

    where each element cijc_{ij} is the sum of the products of elements from the ii-th row of D1D_1 and the corresponding elements from the jj-th row of D2D_2,

    i.e.

    cij=ai1b1j+ai2b2j++ainbnj.c_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}.

    Proof: Construct a 2n2n-order determinant

    D=a11a12a1n0000a21a22a2n00000000an1an2ann0000100b11b12b1n010b21b22b2n001bn1bn2bnnD = \begin{vmatrix} a_{11} & a_{12} & \cdots &a_{1n} &0&0&0&0\\ a_{21} &a_{22} &\cdots & a_{2n}&0&0&0&0\\ \vdots & \vdots & &\vdots &0&0&0&0\\ a_{n1} & a_{n2} &\cdots & a_{nn} &0&0&0&0\\ -1&0&\cdots &0&b_{11}&b_{12}&\cdots&b_{1n}\\ 0&-1&\dotso&0&b_{21}&b_{22}&\cdots&b_{2n}\\ \vdots & \vdots & &\vdots&\vdots & \vdots &&\vdots \\ 0&0&\cdots&-1 &b_{n1}&b_{n2}&\cdots &b_{nn} \end{vmatrix}

    According to Laplace's theorem, expanding DD by the first nn rows, all of the minors formed by the first nn rows and other elements will be zero except for the minor at the top left, so

    D=a11a12a1na21a22a2nan1an2annb11b12b1nb21b22b2nbn1bn2bnn=D1D2.D = \begin{vmatrix} a_{11} & a_{12} & \cdots &a_{1n} \\ a_{21} &a_{22} &\cdots & a_{2n}\\ \vdots & \vdots & &\vdots \\ a_{n1} & a_{n2} &\cdots & a_{nn}\end{vmatrix}\cdot \begin{vmatrix} b_{11} & b_{12} & \cdots &b_{1n} \\ b_{21} &b_{22} &\cdots & b_{2n}\\ \vdots & \vdots & &\vdots \\ b_{n1} & b_{n2} &\cdots & b_{nn}\end{vmatrix}=D_1D_2.

    Next, we show that D=CD = C. Perform elementary row operations on DD: add the a11a_{11}-multiple of the (n+1)(n+1)-th row, the a12a_{12}-multiple of the (n+2)(n+2)-th row, \dots, and the a1na_{1n}-multiple of the (2n)(2n)-th row to the first row to get

    D=000c11c12c1na21a22a2n00000000an1an2ann0000100b11b12b1n010b21b22b2n001bn1bn2bnn.D = \begin{vmatrix} 0&0&\cdots&0&c_{11}&c_{12}&\cdots&c_{1n}\\ a_{21} &a_{22} &\cdots & a_{2n}&0&0&0&0\\ \vdots & \vdots & &\vdots &0&0&0&0\\ a_{n1} & a_{n2} &\cdots & a_{nn} &0&0&0&0\\ -1&0&\cdots &0&b_{11}&b_{12}&\cdots&b_{1n}\\ 0&-1&\dotso&0&b_{21}&b_{22}&\cdots&b_{2n}\\ \vdots & \vdots & &\vdots&\vdots & \vdots &&\vdots \\ 0&0&\cdots&-1 &b_{n1}&b_{n2}&\cdots &b_{nn} \end{vmatrix}.

    Similarly, successively add the ak1a_{k1}-multiple of the (n+1)(n+1)-th row, the ak2a_{k2}-multiple of the (n+2)(n+2)-th row, \dots, and the akna_{kn}-multiple of the (2n)(2n)-th row to the kk-th row to obtain

    D=000a11a12a1n000a21a22a2n000an1an2ann100b11b12b1n010b21b22b2n001bn1bn2bnn.D = \begin{vmatrix} 0&0&\cdots&0& a_{11} & a_{12} & \cdots &a_{1n} \\ 0&0&\cdots&0&a_{21} &a_{22} &\cdots & a_{2n}\\ \vdots &\vdots & &\vdots &\vdots & \vdots & &\vdots \\ 0&0&\cdots&0&a_{n1} & a_{n2} &\cdots & a_{nn} \\ -1&0&\cdots &0&b_{11}&b_{12}&\cdots&b_{1n}\\ 0&-1&\dotso&0&b_{21}&b_{22}&\cdots&b_{2n}\\ \vdots & \vdots & &\vdots&\vdots & \vdots &&\vdots \\ 0&0&\cdots&-1 &b_{n1}&b_{n2}&\cdots &b_{nn} \end{vmatrix}.

    In this determinant, the first nn rows contain only one non-zero nn-order minor. Therefore, by Laplace's theorem,

    D=c11c12c1nc21c22c2ncn1cn2cnn  (1)(1+2++n)+(n+1+n+2++2n)  100010001=C.D = \begin{vmatrix} c_{11} &c_{12} & \cdots &c_{1n} \\ c_{21} &c_{22} &\cdots & c_{2n}\\ \vdots & \vdots & &\vdots \\ c_{n1} & c_{n2} &\cdots & c_{nn}\end{vmatrix} ~\\ ~\\ \ast (-1)^{(1+2+\cdots+n)+(n+1+n+2+\cdots +2n)} ~\\ ~\\ \ast \begin{vmatrix} -1 & 0 & \cdots & 0\\ 0 & -1 & \cdots & 0\\ \vdots & \vdots & &\vdots \\ 0& 0 & \cdots &-1 \end{vmatrix} = C.