Prove $\det(I_n + A) = 1 + \sum_{\emptyset \neq J \subset [n]} \det(A_J)$ In the paper Royen's proof of the Gaussian correlation inequality the first part of Lemma 5 states

For any matrix $A \in M_{n\times n}$,
  $$\det(I_n + A) = 1 + \sum_{\emptyset \neq J \subset [n]} \det(A_J).$$

where $A_J$ is defined as the submatrix of $A$ with row and columns indices $i \in J$, and where $[n] := \{1, \ldots, n\}$. In the paper it is suggested that this can be proved by induction on $n$ or, alternatively, by using the Leibniz formula for the determinant.
I would like to know how this can be proved by induction. My initial idea was to use the Laplace expansion for the determinant to write the determinant on the LHS as a linear combination of determinants of submatrices, and that these determinants of submatrices could be substituted with the inductive hypothesis, assumed true for $(n-1) \times (n-1)$ matrices. However, only one of the submatrices is of the right form, being the sum of a submatrix of $A$ and the identity matrix.
 A: First, I'll write that identity as $\det(I_n + A) = \sum_{J \subseteq\{1,2,\ldots,n\}} \det(A_J)$ for clarity.
You need to get a summation over $2^n$ terms, while you have $2$ terms in inside the determinant; it is therefore useful to successively apply multi-linearity with respect to each of the $n$ columns (this is similar to expanding a product of $n$ binomials using distributivity, giving $2^n$ terms). Applying it for the first column, one gets $\det(I_n+A)=\det(A_0)+\det(A_1)$ where $A_0$ is the result of replacing the first column of $A+I$ by the first column of $I_n$, and $A_1$ is the result of replacing the first column of $A+I$ by the first column of $A$. Repeat this for each column, giving $2^n$ terms which we label by the subset $J$ of column indices for which we have replaced the column by that of $A$ rather than of $I_n$. I will write that term as $\det(A[J])$ where $A[J]$ is the matrix obtained from$~A$ by replacing all columns with index in the complement of $J$ by the corresponding column of$~I_n$, then we have obtained
$$\det(I_n + A) = \sum_{J \subseteq\{1,2,\ldots,n\}} \det(A[J]).$$
It remains to show that $\det(A[J])=\det(A_J)$, the principal minor of $A$ for the rows and columns indexed by$~J$. This means we must remove from $A[J]$ the columns that were taken from $I_n$ and the rows in which those columns have an entry$~1$. But for a given such column, it is immediate that Laplace expansion by that column does precisely that (remove the column and the row where it has a entry$~1$).

The repeated expansion by linearity in each of the columns could of course (and should if we want a formal proof) be formulated in the form of a proof by induction. If one considers the argument used, it becomes clear however that this requires a bit of induction loading: strengthening the statement to be proved for the sole purpose of making the inductive argument possible. The statement will involve an additional parameter $K\subseteq\{1,2,\ldots,n\}$ which in the final application will be taken to be the whole set, and the induction will be by the size of the set$~K$. The statement to prove by induction then becomes the following, using above notation and in addition $I_K$ to stand for the $n\times n$ diagonal matrix whose diagonal entry at position $i$ is $1$ if $i\in K$, and $0$ otherwise:
$$
  \det(A+I_K) = \sum_{J\subseteq K} A[J\cup\overline K]
$$
(the bar designates the set complement inside $\{1,2,\ldots,n\}$). The proof by induction is now straightforward. The starting case $K=\emptyset$ holds by definition (the sum has a single term $J=\emptyset$), and for the inductive step with $K\neq\emptyset$ one writes $K=K^-\cup\{k\}$ (with of course $k\notin K^-$), then applies linearity in column $k$ giving $\det(A+I_K)=\det(A+I_{K^-})+\det(A'+I_{K^-})$ where $A'=A[\overline{\{k\}}]$ is obtained from $A$ by replacing column $k$ by that of $I_n$; then by induction the first term $\det(A+I_{K^-})$ gives the sum of terms $\det(A[J\cup\overline{K^-}])$ for those $J\subseteq K$ that contain$~k$, while the second term $\det(A'+I_{K^-})$ gives a similar sum for those $J\subseteq K$ that do not contain$~k$. I'll leave the (simple but somewhat confusing due to the complements taken) details as an exercise, noting just that the proof for the second term uses that $A'[J\cup\{k\}\cup\overline K]=A[J\cup\overline K]$ when $k\notin J$.
