Laplace's Expansion Theorem

From ProofWiki
Jump to: navigation, search

Theorem

Let $D$ be the determinant of order $n$.

Let $r_1, r_2, \ldots, r_k$ be integers such that:

$1 \le k < n$
$1 \le r_1 < r_2 < \cdots < r_k \le n$

Let $D \left({r_1, r_2, \ldots, r_k \mid u_1, u_2, \ldots, u_k}\right)$ be an order-$k$ minor of $D$.

Let $\tilde D \left({r_1, r_2, \ldots, r_k \mid u_1, u_2, \ldots, u_k}\right)$ be the cofactor of $D \left({r_1, r_2, \ldots, r_k | u_1, u_2, \ldots, u_k}\right)$.


Then:

$\displaystyle D = \sum_{1 \mathop \le u_1 \mathop < \cdots \mathop < u_k \mathop \le n} D \left({r_1, r_2, \ldots, r_k \mid u_1, u_2, \ldots, u_k}\right) \tilde D \left({r_1, r_2, \ldots, r_k \mid u_1, u_2, \ldots, u_k}\right)$


A similar result applies for columns.


Proof

Let us define $r_{k+1}, r_{k+2}, \ldots, r_n$ such that

$1 \le r_{k+1} < r_{k+2} < \cdots < r_n \le n$
$\rho = \left({r_1, r_2, \ldots, r_n}\right)$ is a permutation on $\N^*_n$.

Let $\sigma = \left({s_1, s_2, \ldots, s_n}\right)$ be a permutation on $\N^*_n$.

Then by Permutation of Determinant Indices we have:

\(\displaystyle D\) \(=\) \(\displaystyle \sum_\sigma \operatorname{sgn} \left({\rho}\right) \operatorname{sgn} \left({\sigma}\right) \prod_{j \mathop = 1}^n a_{\rho \left({j}\right) \sigma \left({j}\right)}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_\sigma \left({-1}\right)^{\sum_{i \mathop = 1}^k \left({r_i + s_i}\right)} \operatorname{sgn} \left({\rho \left({r_1, \ldots, r_k}\right)}\right) \operatorname{sgn} \left({\sigma \left({s_1,\ldots, s_k}\right)}\right) \operatorname{sgn} \left({\rho \left({r_{k+1},\ldots, r_n}\right)}\right) \operatorname{sgn} \left({\sigma \left({s_{k+1},\ldots, s_n}\right)}\right) \prod_{j \mathop = 1}^n a_{\rho \left({j}\right) \sigma \left({j}\right)}\) $\quad$ $\quad$

We can get all the permutations $\sigma$ exactly once by separating the numbers $1, \ldots, n$ in all possible ways into a set of $k$ and $n-k$ numbers.

We let $\left({s_1, \ldots, s_k}\right)$ vary over the first set and $\left({s_{k+1}, \ldots, s_n}\right)$ over the second set.

So the summation over all $\sigma$ can be replaced by:

$\left({u_1, \ldots, u_n}\right) = \sigma \left({1, \ldots, n}\right)$
$u_1 < u_2 < \cdots < u_k, u_{k+1} < u_{k+2} < \cdots < u_n$
$\left({s_1,\ldots, s_k}\right) = \sigma \left({u_1, \ldots, u_k}\right)$
$\left({s_{k+1},\ldots, s_n}\right) = \sigma \left({u_{k+1}, \ldots, u_n}\right)$


Thus we get:

\(\displaystyle D\) \(=\) \(\displaystyle \sum_{\sigma \left({u_1, \ldots, u_n}\right)} \left({-1}\right)^{\sum_{i \mathop = 1}^k \left({r_i + u_i}\right)} \sum_{\sigma \left({u_1, \ldots, u_k}\right)} \operatorname{sgn} \left({\rho \left({r_1, \ldots, r_k}\right)}\right) \operatorname{sgn} \left({\sigma \left({s_1, \ldots, s_k}\right)}\right)\prod_{j \mathop = 1}^k a_{\rho \left({j}\right) \sigma \left({j}\right)}\) $\quad$ $\quad$
\(\displaystyle \) \(\times\) \(\displaystyle \sum_{\sigma \left({u_{k+1}, \ldots, u_n}\right)} \operatorname{sgn} \left({\rho \left({r_{k+1},\ldots, r_n}\right)}\right) \operatorname{sgn} \left({\sigma \left({s_{k+1},\ldots, s_n}\right)}\right)\prod_{j \mathop = k+1}^n a_{\rho \left({j}\right) \sigma \left({j}\right)}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{\sigma \left({u_1, \ldots, u_n}\right)} \left({-1}\right)^{\sum_{i \mathop = 1}^k \left({r_i + u_i}\right)} \begin{vmatrix} a_{r_1 u_1} & \cdots & a_{r_1 u_k} \\ \vdots & \ddots & \vdots \\ a_{r_k u_1} & \cdots & a_{r_k u_k} \end{vmatrix} \times \begin{vmatrix}a_{r_{k+1} u_{k+1} } & \cdots & a_{r_{k+1} u_n} \\ \vdots & \ddots & \vdots \\ a_{r_n u_{k+1} } & \cdots & a_{r_n u_n} \end{vmatrix}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{\sigma \left({u_1, \ldots, u_n}\right)} \left({-1}\right)^{\sum_{i\mathop = 1}^k \left({r_i + u_i}\right)} D \left({r_1, \ldots, r_k \mid u_1, \ldots, u_k}\right) \times D \left({r_{k+1}, \ldots, r_n \mid u_{k+1}, \ldots, u_n}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{\sigma \left({u_1, \ldots, u_n}\right)} D \left({r_1, \ldots, r_k \mid u_1, \ldots, u_k}\right) \times \tilde D \left({r_1, \ldots, r_k \mid u_1, \ldots, u_k}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{1 \mathop \le u_1 \mathop < \cdots \mathop < u_k \mathop \le n} D \left({r_1, \ldots, r_k \mid u_1, \ldots, u_k}\right) \tilde D \left({r_1, \ldots, r_k \mid u_1, \ldots, u_k}\right) \sum_{u_{k+1}, \ldots, u_n} 1\) $\quad$ $\quad$

That last inner sum extends over all integers which satisfy:

$\left({u_1, \ldots, u_n}\right) = \sigma \left({1, \ldots, n}\right)$
$u_1 < u_2 < \cdots < u_k, u_{k+1} < u_{k+2} < \cdots < u_n$

But for each set of $u_1, \ldots, u_k$, then the integers $u_{k+1}, \ldots, u_n$ are clearly uniquely determined.

So that last inner sum equals 1 and the theorem is proved.



The result for columns follows from Determinant of Transpose.

$\blacksquare$


Comment

This gives us an expansion of the determinant $D$ in terms of $k$ specified rows.

We form all possible order-$k$ minors of $D$ which involve all of these rows, and multiply each of them by their cofactors.

The sum of these products is equal to $D$.

We note that when $k = 1$ this becomes the Expansion Theorem for Determinants.


Examples

Let $\mathbf A$ be the matrix defined as:

$\mathbf A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}$

Then $\det \left({\mathbf A}\right)$ can be calculated using Laplace's Expansion Theorem as follows.


Expanding row $2$:

\(\displaystyle \det \left({\mathbf A}\right)\) \(=\) \(\displaystyle \left({-1}\right)^{2 + 1} \times 4 \begin{vmatrix} 2 & 3 \\ 8 & 9 \end{vmatrix}\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^{2 + 2} \times 5 \begin{vmatrix} 1 & 3 \\ 7 & 9 \end{vmatrix}\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^{2 + 3} \times 6 \begin{vmatrix} 1 & 2 \\ 7 & 8 \end{vmatrix}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle - 4 \left({2 \times 9 - 3 \times 8}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle 5 \left({1 \times 9 - 3 \times 7}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle - \, \) \(\displaystyle 6 \left({1 \times 8 - 2 \times 7}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 4 \left({24 - 18}\right) + 5 \left({9 - 21}\right) + 6 \left({14 - 8}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 0\) $\quad$ $\quad$

This shows that $\mathbf A$ is non-invertible.


Also known as

This theorem is also known as the Laplace cofactor expansion.


Source of Name

This entry was named for Pierre-Simon de Laplace.


Sources