Cofactor Sum Identity

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $J_n$ be the $n \times n$ matrix of all ones.

Let $A$ be an $n \times n$ matrix.

Let $A_{ij}$ denote the cofactor of element $\paren {i,j}$ in $\det\paren A$, $1\le i,j \le n$.


Then:

$\displaystyle \det \paren {A -J_n} = \det \paren A - \sum_{i \mathop = 1}^n \sum_{j \mathop = 1}^n A_{ij} $


Proof

Let $P_j$ equal matrix $A$ with column $j$ replaced by ones, $1\le j \le n$.

Then:

\(\displaystyle \sum_{j \mathop = 1}^n \det\paren { P_j }\) \(=\) \(\displaystyle \sum_{j \mathop = 1}^n \sum_{i \mathop = 1}^n A_{ij}\) Cofactor expansion applied to column $j$ of $P_j$.

To complete the proof it suffices to prove the equivalent identity:

$\displaystyle \det\paren {A -J_n} = \det\paren A - \sum_{j \mathop = 1}^n \det\paren { P_j }$

Expansion of left side $\det\paren { A - J_n}$ for the $2\times 2$ case illustrates how determinant theorems will be used:

\(\displaystyle A\) \(=\) \(\displaystyle \left(\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right)\) Symbol $A$ is any $2\times 2$ matrix.
\(\displaystyle J_2\) \(=\) \(\displaystyle \left(\begin{smallmatrix} 1 & 1 \\ 1 & 1 \end{smallmatrix}\right)\) Symbol $J_2$ is the $2\times 2$ matrix of all ones.
\(\displaystyle \det\paren {A -J_2}\) \(=\) \(\displaystyle \det\paren { \begin{smallmatrix} a-1 & b-1 \\ c-1 & d-1 \end{smallmatrix} }\) Matrix subtraction.
\(\displaystyle \) \(=\) \(\displaystyle \det\paren { \begin{smallmatrix} a & b-1 \\ c & d-1 \end{smallmatrix} } - \det\paren { \begin{smallmatrix} 1 & b-1 \\ 1 & d-1 \end{smallmatrix} }\) Determinant as Sum of Determinants
\(\displaystyle \) \(=\) \(\displaystyle \det\paren { \begin{smallmatrix} a & b-1 \\ c & d-1 \end{smallmatrix} } - \det\paren { \begin{smallmatrix} 1 & b \\ 1 & d \end{smallmatrix} }\) Determinant rule Replacement Rule for Determinant Columns
\(\displaystyle \) \(=\) \(\displaystyle \det\paren { \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} } - \det\paren { \begin{smallmatrix} a & 1 \\ c & 1 \end{smallmatrix} } - \det\paren { \begin{smallmatrix} 1 & b \\ 1 & d \end{smallmatrix} }\) Determinant Linearity in a Column
\(\displaystyle \) \(=\) \(\displaystyle \det\paren A - \det\paren {P_2} - \det\paren { P_1 }\) Definition of $P_1$, $P_2$.
\(\displaystyle \) \(=\) \(\displaystyle \det\paren A - \sum_{j \mathop = 1}^2 \det\paren { P_j }\) Equivalent identity verified for $n = 2$.

Let $A$ be an $n\times n$ matrix.

Let matrix $Q_m$ equal ones matrix $J_n$ with zeros replacing all entries in columns $1$ to $m$.

Example:

\(\displaystyle Q_2\) \(=\) \(\displaystyle \paren { \begin{smallmatrix} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ \end{smallmatrix} }\) Instance $n = 5, m = 2$.

Induction on $m$ will be applied to prove the induction identity:

$\displaystyle \det\paren { A -J_n } = \det\paren { A -Q_m }- \sum_{j \mathop = 1}^m \det\paren { P_j }$, $1\le m \le n$

Induction step $m = 1$:

\(\displaystyle \det\paren { A -J_n }\) \(=\) \(\displaystyle \det\paren { A -Q_1 }- \det\paren { P_1-Q_1 }\) $P_1$ equals $A$ with column $1$ all ones.

Determinant as Sum of Determinants

\(\displaystyle \det\paren { P_1-Q_1 }\) \(=\) \(\displaystyle \det\paren { P_1 }\) Add ones in column 1 to columns $2\cdots n$,

Replacement Rule for Determinant Columns

\(\displaystyle \det\paren { A -J_n }\) \(=\) \(\displaystyle \det\paren { A -Q_1 }- \det\paren { P_1 }\) Combine equations.

Induction step $m = k$ and $k < n$ implies $m = k+1$:

\(\displaystyle \det\paren { A - J_n }\) \(=\) \(\displaystyle \det\paren { A - Q_k }- \sum_{j \mathop = 1}^k \det\paren { P_j }\) Induction hypothesis $m = k$.
\(\displaystyle \det\paren { A -Q_k }\) \(=\) \(\displaystyle \det\paren { A -Q_{k+1} } - \det\paren { P_{k+1} - Q_{k+1} }\) Determinant linearity on column $k+1$.
\(\displaystyle \det\paren { P_{k+1} - Q_{k+1} }\) \(=\) \(\displaystyle \det\paren { P_{k+1} }\) Add ones in column $k+1$ to columns $k+2\cdots n$.

Replacement Rule for Determinant Columns

\(\displaystyle \det\paren { A -J_n }\) \(=\) \(\displaystyle \det\paren { A -Q_{k+1} }-\det\paren { P_{k+1} }- \sum_{j \mathop = 1}^k \det\paren { P_j }\) Combine preceding three equations.
\(\displaystyle \det\paren { A -J_n }\) \(=\) \(\displaystyle \det\paren { A -Q_{k+1} } - \sum_{j \mathop = 1}^{k+1} \det\paren { P_j }\) Induction completed.

Conclusion: Matrix $A-Q_n$ equals $A$ because $Q_n$ is the zero matrix.

Let $m = n$ in the induction identity, then:

$\displaystyle \det\paren { A - J_n } = \det\paren { A }- \sum_{j \mathop = 1}^n \det\paren { P_j }$

$\blacksquare$