Laplace expansion

Proof

Suppose ${\displaystyle B}$ is an n × n matrix and ${\displaystyle i,j\in \{1,2,\dots ,n\}.}$ For clarity we also label the entries of ${\displaystyle B}$ that compose its ${\displaystyle i,j}$ minor matrix ${\displaystyle M_{ij}}$ as

${\displaystyle (a_{st})}$ for ${\displaystyle 1\le s,t\le n-1.}$

Consider the terms in the expansion of ${\displaystyle |B|}$ that have ${\displaystyle b_{ij}}$ as a factor. Each has the form

${\displaystyle \mathrm{sgn}\tau b_{1,\tau (1)}\cdots b_{i,j}\cdots b_{n,\tau (n)}=\mathrm{sgn}\tau b_{ij}{a}_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}}$

for some permutation τ ∈ S_n with ${\displaystyle \tau (i)=j}$, and a unique and evidently related permutation ${\displaystyle \sigma \in S_{n-1}}$ which selects the same minor entries as τ. Similarly each choice of σ determines a corresponding τ i.e. the correspondence ${\displaystyle \sigma \leftrightarrow \tau }$ is a bijection between ${\displaystyle S_{n-1}}$ and ${\displaystyle \{\tau \in S_n:\tau (i)=j\}.}$ Using Cauchy's two-line notation, the explicit relation between ${\displaystyle \tau }$ and ${\displaystyle \sigma }$ can be written as

${\displaystyle \sigma =\left(\begin{array}{cccccc}1& 2& \cdots & i& \cdots & n-1\\ (\leftarrow {)}_j(\tau (1))& (\leftarrow {)}_j(\tau (2))& \cdots & (\leftarrow {)}_j(\tau (i+1))& \cdots & (\leftarrow {)}_j(\tau (n))\end{array}\right)}$

where ${\displaystyle (\leftarrow {)}_j}$ is a temporary shorthand notation for a cycle ${\displaystyle (n,n-1,\cdots ,j+1,j)}$. This operation decrements all indices larger than j so that every index fits in the set {1,2,...,n-1}

The permutation τ can be derived from σ as follows. Define ${\displaystyle {\sigma }^{\prime }\in S_n}$ by ${\displaystyle {\sigma }^{\prime }(k)=\sigma (k)}$ for ${\displaystyle 1\le k\le n-1}$ and ${\displaystyle {\sigma }^{\prime }(n)=n}$. Then ${\displaystyle {\sigma }^{\prime }}$ is expressed as

${\displaystyle {\sigma }^{\prime }=\left(\begin{array}{ccccccc}1& 2& \cdots & i& \cdots & n-1& n\\ (\leftarrow {)}_j(\tau (1))& (\leftarrow {)}_j(\tau (2))& \cdots & (\leftarrow {)}_j(\tau (i+1))& \cdots & (\leftarrow {)}_j(\tau (n))& n\end{array}\right)}$

Now, the operation which apply ${\displaystyle (\leftarrow {)}_i}$ first and then apply ${\displaystyle {\sigma }^{\prime }}$ is (Notice applying A before B is equivalent to applying inverse of A to the upper row of B in two-line notation)

${\displaystyle {\sigma }^{\prime }(\leftarrow {)}_i=\left(\begin{array}{ccccccc}1& 2& \cdots & i+1& \cdots & n& i\\ (\leftarrow {)}_j(\tau (1))& (\leftarrow {)}_j(\tau (2))& \cdots & (\leftarrow {)}_j(\tau (i+1))& \cdots & (\leftarrow {)}_j(\tau (n))& n\end{array}\right)}$

where ${\displaystyle (\leftarrow {)}_i}$ is temporary shorthand notation for ${\displaystyle (n,n-1,\cdots ,i+1,i)}$.

the operation which applies ${\displaystyle \tau }$ first and then applies ${\displaystyle (\leftarrow {)}_j}$ is

${\displaystyle (\leftarrow {)}_j\tau =\left(\begin{array}{ccccccc}1& 2& \cdots & i& \cdots & n-1& n\\ (\leftarrow {)}_j(\tau (1))& (\leftarrow {)}_j(\tau (2))& \cdots & n& \cdots & (\leftarrow {)}_j(\tau (n-1))& (\leftarrow {)}_j(\tau (n))\end{array}\right)}$

above two are equal thus,

${\displaystyle (\leftarrow {)}_j\tau ={\sigma }^{\prime }(\leftarrow {)}_i}$

${\displaystyle \tau =(\to {)}_j{\sigma }^{\prime }(\leftarrow {)}_i}$

where ${\displaystyle (\to {)}_j}$ is the inverse of ${\displaystyle (\leftarrow {)}_j}$ which is ${\displaystyle (j,j+1,\cdots ,n)}$.

Thus

${\displaystyle \tau =(j,j+1,\dots ,n){\sigma }^{\prime }(n,n-1,\dots ,i)}$

Since the two cycles can be written respectively as ${\displaystyle n-i}$ and ${\displaystyle n-j}$ transpositions,

${\displaystyle \mathrm{sgn}\tau =(-1{)}^{2n-(i+j)}\mathrm{sgn}{\sigma }^{\prime }=(-1{)}^{i+j}\mathrm{sgn}\sigma .}$

And since the map ${\displaystyle \sigma \leftrightarrow \tau }$ is bijective,

${\displaystyle \begin{array}{cc}\sum _{i=1}^n\sum _{\tau \in S_n:\tau (i)=j}\mathrm{sgn}\tau b_{1,\tau (1)}\cdots b_{n,\tau (n)}& =\sum _{i=1}^n\sum _{\sigma \in S_{n-1}}(-1{)}^{i+j}\mathrm{sgn}\sigma b_{ij}{a}_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\ & =\sum _{i=1}^n{b}_{ij}(-1{)}^{i+j}\sum _{\sigma \in S_{n-1}}\mathrm{sgn}\sigma a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\ & =\sum _{i=1}^n{b}_{ij}(-1{)}^{i+j}{M}_{ij}\end{array}}$

from which the result follows. Similarly, the result holds if the index of the outer summation was replaced with ${\displaystyle j}$.

Laplace expansion of a determinant by complementary minors

Laplace's cofactor expansion can be generalised as follows.

Example

Consider the matrix

${\displaystyle A=\left[\begin{array}{cccc}1& 2& 3& 4\\ 5& 6& 7& 8\\ 9& 10& 11& 12\\ 13& 14& 15& 16\end{array}\right].}$

The determinant of this matrix can be computed by using the Laplace's cofactor expansion along the first two rows as follows. Firstly note that there are 6 sets of two distinct numbers in {1, 2, 3, 4}, namely let ${\displaystyle S=\left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\right\}}$ be the aforementioned set.

By defining the complementary cofactors to be

${\displaystyle b_{\{j,k\}}=\left|\begin{array}{cc}{a}_{1j}& a_{1k}\\ a_{2j}& a_{2k}\end{array}\right|,}$

${\displaystyle c_{\{p,q\}}=\left|\begin{array}{cc}{a}_{3p}& a_{3q}\\ a_{4p}& a_{4q}\end{array}\right|,}$

and the sign of their permutation to be

${\displaystyle {\epsilon }^{\{j,k\},\{p,q\}}=\mathrm{sgn}\left[\begin{array}{cccc}1& 2& 3& 4\\ j& k& p& q\end{array}\right],\text{ where }p\ne j,q\ne k.}$

The determinant of A can be written out as

${\displaystyle |A|=\sum _{H\in S}{\epsilon }^{H,H^{\mathrm{\prime }}}{b}_H{c}_{H^{\mathrm{\prime }}},}$

where ${\displaystyle H^{\mathrm{\prime }}}$ is the complementary set to ${\displaystyle H}$.

In our explicit example this gives us

${\displaystyle \begin{array}{cc}|A|& =b_{\{1,2\}}{c}_{\{3,4\}}-b_{\{1,3\}}{c}_{\{2,4\}}+b_{\{1,4\}}{c}_{\{2,3\}}+b_{\{2,3\}}{c}_{\{1,4\}}-b_{\{2,4\}}{c}_{\{1,3\}}+b_{\{3,4\}}{c}_{\{1,2\}}\\ & =\left|\begin{array}{cc}1& 2\\ 5& 6\end{array}\right|\cdot \left|\begin{array}{cc}11& 12\\ 15& 16\end{array}\right|-\left|\begin{array}{cc}1& 3\\ 5& 7\end{array}\right|\cdot \left|\begin{array}{cc}10& 12\\ 14& 16\end{array}\right|+\left|\begin{array}{cc}1& 4\\ 5& 8\end{array}\right|\cdot \left|\begin{array}{cc}10& 11\\ 14& 15\end{array}\right|+\left|\begin{array}{cc}2& 3\\ 6& 7\end{array}\right|\cdot \left|\begin{array}{cc}9& 12\\ 13& 16\end{array}\right|-\left|\begin{array}{cc}2& 4\\ 6& 8\end{array}\right|\cdot \left|\begin{array}{cc}9& 11\\ 13& 15\end{array}\right|+\left|\begin{array}{cc}3& 4\\ 7& 8\end{array}\right|\cdot \left|\begin{array}{cc}9& 10\\ 13& 14\end{array}\right|\\ & =-4\cdot (-4)-(-8)\cdot (-8)+(-12)\cdot (-4)+(-4)\cdot (-12)-(-8)\cdot (-8)+(-4)\cdot (-4)\\ & =16-64+48+48-64+16=0.\end{array}}$

As above, it is easy to verify that the result is correct: the matrix is singular because the sum of its first and third column is twice the second column, and hence its determinant is zero.

General statement

Let ${\displaystyle B=[b_{ij}]}$ be an n × n matrix and ${\displaystyle S}$ the set of k-element subsets of {1, 2, ... , n}, ${\displaystyle H}$ an element in it. Then the determinant of ${\displaystyle B}$ can be expanded along the k rows identified by ${\displaystyle H}$ as follows:

${\displaystyle |B|=\sum _{L\in S}{\epsilon }^{H,L}{b}_{H,L}{c}_{H,L}}$

where ${\displaystyle {\epsilon }^{H,L}}$ is the sign of the permutation determined by ${\displaystyle H}$ and ${\displaystyle L}$, equal to ${\displaystyle (-1{)}^{\left(\sum _{h\in H}h\right)+\left(\sum _{\ell \in L}\ell \right)}}$, ${\displaystyle b_{H,L}}$ the square minor of ${\displaystyle B}$ obtained by deleting from ${\displaystyle B}$ rows and columns with indices in ${\displaystyle H}$ and ${\displaystyle L}$ respectively, and ${\displaystyle c_{H,L}}$ (called the complement of ${\displaystyle b_{H,L}}$) defined to be ${\displaystyle b_{H^{\prime },L^{\prime }}}$ , ${\displaystyle H^{\prime }}$ and ${\displaystyle L^{\prime }}$ being the complement of ${\displaystyle H}$ and ${\displaystyle L}$ respectively.

This coincides with the theorem above when ${\displaystyle k=1}$. The same thing holds for any fixed k columns.

Computational complexity

The Laplace expansion is computationally inefficient for high-dimension matrices, with a time complexity in big O notation of O(n!). Alternatively, using a decomposition into triangular matrices as in the LU decomposition can yield determinants with a time complexity of O(n³). The following Python code implements the Laplace expansion:

<span id="mw9g"></span><span class="k" id="mw9w">def</span><span class="w" id="mw-A"> </span><span class="nf" id="mw-Q">determinant</span><span class="p" id="mw-g">(</span><span class="n" id="mw-w">M</span><span class="p" id="mw_A">):</span> <span class="c1" id="mw_Q"># Base case of recursive function: 1x1 matrix</span> <span class="k" id="mw_g">if</span> <span class="nb" id="mw_w">len</span><span class="p" id="mwAQA">(</span><span class="n" id="mwAQE">M</span><span class="p" id="mwAQI">)</span> <span class="o" id="mwAQM">==</span> <span class="mi" id="mwAQQ">1</span><span class="p" id="mwAQU">:</span> <span class="k" id="mwAQY">return</span> <span class="n" id="mwAQc">M</span><span class="p" id="mwAQg">[</span><span class="mi" id="mwAQk">0</span><span class="p" id="mwAQo">][</span><span class="mi" id="mwAQs">0</span><span class="p" id="mwAQw">]</span> <span class="n" id="mwAQ0">total</span> <span class="o" id="mwAQ4">=</span> <span class="mi" id="mwAQ8">0</span> <span class="k" id="mwARA">for</span> <span class="n" id="mwARE">column</span><span class="p" id="mwARI">,</span> <span class="n" id="mwARM">element</span> <span class="ow" id="mwARQ">in</span> <span class="nb" id="mwARU">enumerate</span><span class="p" id="mwARY">(</span><span class="n" id="mwARc">M</span><span class="p" id="mwARg">[</span><span class="mi" id="mwARk">0</span><span class="p" id="mwARo">]):</span> <span class="c1" id="mwARs"># Exclude first row and current column.</span> <span class="n" id="mwARw">K</span> <span class="o" id="mwAR0">=</span> <span class="p" id="mwAR4">[</span><span class="n" id="mwAR8">x</span><span class="p" id="mwASA">[:</span><span class="n" id="mwASE">column</span><span class="p" id="mwASI">]</span> <span class="o" id="mwASM">+</span> <span class="n" id="mwASQ">x</span><span class="p" id="mwASU">[</span><span class="n" id="mwASY">column</span> <span class="o" id="mwASc">+</span> <span class="mi" id="mwASg">1</span> <span class="p" id="mwASk">:]</span> <span class="k" id="mwASo">for</span> <span class="n" id="mwASs">x</span> <span class="ow" id="mwASw">in</span> <span class="n" id="mwAS0">M</span><span class="p" id="mwAS4">[</span><span class="mi" id="mwAS8">1</span><span class="p" id="mwATA">:]]</span> <span class="n" id="mwATE">s</span> <span class="o" id="mwATI">=</span> <span class="mi" id="mwATM">1</span> <span class="k" id="mwATQ">if</span> <span class="n" id="mwATU">column</span> <span class="o" id="mwATY">%</span> <span class="mi" id="mwATc">2</span> <span class="o" id="mwATg">==</span> <span class="mi" id="mwATk">0</span> <span class="k" id="mwATo">else</span> <span class="o" id="mwATs">-</span><span class="mi" id="mwATw">1</span> <span class="n" id="mwAT0">total</span> <span class="o" id="mwAT4">+=</span> <span class="n" id="mwAT8">s</span> <span class="o" id="mwAUA">*</span> <span class="n" id="mwAUE">element</span> <span class="o" id="mwAUI">*</span> <span class="n" id="mwAUM">determinant</span><span class="p" id="mwAUQ">(</span><span class="n" id="mwAUU">K</span><span class="p" id="mwAUY">)</span> <span class="k" id="mwAUc">return</span> <span class="n" id="mwAUg">total</span>