Determinant of $I+A$

Question

I read that $$|I+A|=1+\sum |A_I|$$ where $A_I$ are all principal submatrices of $A$.

I don't quite see how to prove this idea. Intuition says induction but it does not seem to work.

Answer 1

Depending on your level and experience, this answer might be beyond what you were looking for (or using too much new notation). This responds has been significantly edited, so the comments below may not make as much sense as before.

Sketch:

• Recall that the determinant can be written in terms of permutations. Let $N=\{1,\cdots,n\}$ and $X=I+A$. Then, $$ |X|=\sum_{\sigma\in S_N}\operatorname{sgn}(\sigma)\prod_{i\in N}x_{i\sigma(i)}. $$
• For $\sigma\in S_N$, let $\operatorname{Fix}(\sigma)=\{i\in N:\sigma(i)=i\}$, i.e., the set of indices where $\sigma$ doesn't change the index. Let $\mathcal{P}(S)$ be the power set of $S$, in other words, the set of all subsets of the set $S$. Finally, $\operatorname{Fix}(\sigma)^c=\{i\in N:\sigma(i)\not=i\}$, i.e., the elements which are not fixed by $\sigma$ (and the complement of $\operatorname{Fix}(\sigma)$ in $N$).
• Observe that $x_{i\sigma(i)}=\begin{cases}a_{i\sigma(i)}&i\in\operatorname{Fix}(\sigma)^c\\1+a_{ii}&\operatorname{Fix}(\sigma)\end{cases}$. Therefore, in the determinant formulation, we can distribute the sums in the $1+a_{ii}$'s and write out the sum with more terms: $$ |X|=\sum_{\sigma\in S_N}\operatorname{sgn}(\sigma)\sum_{C\subseteq\mathcal{P}(\operatorname{Fix}(\sigma))}\prod_{j\in C}a_{jj}\prod_{k\in\operatorname{Fix}(\sigma)^c}a_{k\sigma(k)}. $$ In this case, for each index $j$ in $\operatorname{Fix}(\sigma)$, we can either take $1$ or $a_{jj}$. $C$ consists of those indices in $\operatorname{Fix}(\sigma)$ which $a_{jj}$ is chosen (and $\operatorname{Fix}(\sigma)\setminus C$ consists of those indices in $\operatorname{Fix}(\sigma)$ for which $1$ is chosen).
• We now reorganize this sum so that the outer sum is $C$. In particular, we have that the determinant is $$ 1+\sum_{D\in\mathcal{P}(N)\setminus\{N\}}\sum_{\tau\in S_{N\setminus D}}\operatorname{sgn}(\tau)\prod_{l\in N\setminus D}a_{l\tau(l)}. $$ In other words, $D$ is the set $\operatorname{Fix}(\sigma)\setminus C$, i.e., the diagonal entries where $1$ is chosen. $\tau$ is a permutation acting on only $N\setminus D$, the remaining elements (there is a corresponding permutation in $S_N$ which fixes $D$ and acts as $\tau$ on $N\setminus D$; this permutation has the same sign as $\tau$). Note that $\tau$ may fix additional elements in $N\setminus D$. The $1+$ occurs because when $D=N$, the sum is empty, but this corresponds to only choosing $1$'s on the diagonal (i.e., the identity matrix) and the product of the $1$'s is $1$.
• Observe that $$ \sum_{\tau\in S_{N\setminus D}}\operatorname{sgn}(\tau)\prod_{l\in N\setminus D}a_{l\tau(l)} $$ is the determinant $A_{N\setminus D}$, the principal submatrix consisting of the rows and columns in $N\setminus D$. Therefore, the determinant can be rewritten as $$ 1+\sum_{D\in\mathcal{P}(N)\setminus\{N\}}|A_{N\setminus D}|. $$ This matches the form for the original question.