Laplace expansion

Consider the matrix : B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}. The determinant of this matrix can be computed by using the Laplace expansion along any one of its rows or columns. For instance, an expansion along the first row yields: : \begin{align} & = 1 \cdot (-3) - 2 \cdot (-6) + 3 \cdot (-3) = 0. \end{align} Laplace expansion along the second column yields the same result: : \begin{align} & = -2 \cdot (-6) + 5 \cdot (-12) - 8 \cdot (-6) = 0. \end{align} 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. ==Proof==

Suppose B is an n × n matrix and i,j\in\{1,2,\dots,n\}. For clarity we also label the entries of B that compose its i,j minor matrix M_{ij} as (a_{st}) for 1 \le s,t \le n-1. Consider the terms in the expansion of |B| that have b_{ij} as a factor. Each has the form : \sgn \tau\,b_{1,\tau(1)} \cdots b_{i,j} \cdots b_{n,\tau(n)} = \sgn \tau\,b_{ij} a_{1,\sigma(1)} \cdots a_{n-1,\sigma(n-1)} for some permutation with \tau(i)=j, and a unique and evidently related permutation \sigma\in S_{n-1} which selects the same minor entries as . Similarly each choice of determines a corresponding i.e. the correspondence \sigma\leftrightarrow\tau is a bijection between S_{n-1} and \{\tau\in S_n\colon\tau(i)=j\}. Using Cauchy's two-line notation, the explicit relation between \tau and \sigma can be written as : \sigma = \begin{pmatrix} 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{pmatrix} where (\leftarrow)_j is a temporary shorthand notation for a cycle (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 \sigma'\in S_n by \sigma'(k) = \sigma(k) for 1 \le k \le n-1 and \sigma'(n) = n. Then \sigma' is expressed as : \sigma' = \begin{pmatrix} 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{pmatrix} Now, the operation which apply (\leftarrow)_i first and then apply \sigma' is (Notice applying A before B is equivalent to applying inverse of A to the upper row of B in two-line notation) : \sigma' (\leftarrow)_i = \begin{pmatrix} 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{pmatrix} where (\leftarrow)_i is temporary shorthand notation for (n,n-1,\cdots,i+1,i). the operation which applies \tau first and then applies (\leftarrow)_j is : (\leftarrow)_j \tau = \begin{pmatrix} 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{pmatrix} above two are equal thus, : (\leftarrow)_j \tau = \sigma' (\leftarrow)_i : \tau = (\rightarrow)_j \sigma' (\leftarrow)_i where (\rightarrow)_j is the inverse of (\leftarrow)_j which is (j,j+1,\cdots,n). Thus : \tau\,=(j,j+1,\ldots,n)\sigma'(n,n-1,\ldots,i) Since the two cycles can be written respectively as n-i and n-j transpositions, : \sgn\tau\,= (-1)^{2n-(i+j)} \sgn\sigma'\,= (-1)^{i+j} \sgn\sigma. And since the map \sigma\leftrightarrow\tau is bijective, :\begin{align} \sum_{i=1}^n\sum_{\tau \in S_n:\tau(i)=j} \sgn \tau\,b_{1,\tau(1)} \cdots b_{n,\tau(n)} &= \sum_{i=1}^{n}\sum_{\sigma \in S_{n-1}} (-1)^{i+j}\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}} \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{align} from which the result follows. Similarly, the result holds if the index of the outer summation was replaced with j. ==Laplace expansion of a determinant by complementary minors==

Laplace's cofactor expansion can be generalised as follows. Example Consider the matrix : A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix}. 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 {{math|{1, 2, 3, 4},}} namely let 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 : b_{\{j,k\}}=\begin{vmatrix} a_{1j} & a_{1k} \\ a_{2j} & a_{2k} \end{vmatrix}, : c_{\{p,q\}}=\begin{vmatrix} a_{3p} & a_{3q} \\ a_{4p} & a_{4q} \end{vmatrix}, and the sign of their permutation to be : \varepsilon^{\{j,k\},\{p,q\}} = \sgn\begin{bmatrix} 1 & 2 & 3 & 4 \\ j & k & p & q \end{bmatrix}, \text{ where } p\neq j,q\neq k. The determinant of A can be written out as : |A| = \sum_{H \in S} \varepsilon^{H,H^\prime}b_{H}c_{H^\prime}, where H^{\prime} is the complementary set to H . In our explicit example this gives us :\begin{align} &= \begin{vmatrix} 1 & 2 \\ 5 & 6 \end{vmatrix} \cdot \begin{vmatrix} 11 & 12 \\ 15 & 16 \end{vmatrix} - \begin{vmatrix} 1 & 3 \\ 5 & 7 \end{vmatrix} \cdot \begin{vmatrix} 10 & 12 \\ 14 & 16 \end{vmatrix} + \begin{vmatrix} 1 & 4 \\ 5 & 8 \end{vmatrix} \cdot \begin{vmatrix} 10 & 11 \\ 14 & 15 \end{vmatrix} + \begin{vmatrix} 2 & 3 \\ 6 & 7 \end{vmatrix} \cdot \begin{vmatrix} 9 & 12 \\ 13 & 16 \end{vmatrix} - \begin{vmatrix} 2 & 4 \\ 6 & 8 \end{vmatrix} \cdot \begin{vmatrix} 9 & 11 \\ 13 & 15 \end{vmatrix} + \begin{vmatrix} 3 & 4 \\ 7 & 8 \end{vmatrix} \cdot \begin{vmatrix} 9 & 10 \\ 13 & 14 \end{vmatrix}\\[5pt] &= -4 \cdot (-4) -(-8) \cdot (-8) +(-12) \cdot (-4) +(-4) \cdot (-12) -(-8) \cdot (-8) +(-4) \cdot (-4)\\[5pt] &= 16 - 64 + 48 + 48 - 64 + 16 = 0. \end{align} 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 B=[b_{ij}] be an matrix and S the set of -element subsets of , H an element in it. Then the determinant of B can be expanded along the rows identified by H as follows: :|B| = \sum_{L\in S} \varepsilon^{H,L} b_{H,L} c_{H,L} where \varepsilon^{H,L} is the sign of the permutation determined by H and L, equal to (-1)^{\left(\sum_{h\in H}h\right) + \left(\sum_{\ell\in L}\ell\right)}, b_{H,L} the square minor of B obtained by deleting from B rows and columns with indices in H and L respectively, and c_{H,L} (called the complement of b_{H,L}) defined to be b_{H',L'} , H' and L' being the complement of H and L respectively. This coincides with the theorem above when k=1. The same thing holds for any fixed columns. ==Computational complexity==

The Laplace expansion is computationally inefficient for high-dimension matrices, with a time complexity in big O notation of . Alternatively, using a decomposition into triangular matrices as in the LU decomposition can yield determinants with a time complexity of . The following Python code implements the Laplace expansion: def determinant(M): # Base case of recursive function: 1x1 matrix if len(M) == 1: return M[0][0] total = 0 for column, element in enumerate(M[0]): # Exclude first row and current column. K = [x[:column] + x[column + 1 :] for x in M[1: s = 1 if column % 2 == 0 else -1 total += s * element * determinant(K) return total ==See also==