Here is a piece of useful notation. Suppose that $i$, $j$ are two integers. We define
$$
\rho(i, j)
= \begin{cases}
0, & i < j; \\
1, & i \geq j.
\end{cases}
$$
Proof of Theorem 1. Let the proposition $P(n)$ be as follows:
For any $n \times n$ matrix $A$ and for any positive integer $j$ less than or equal to $n$,
$$
\det {(A)} = \sum_{i = 1}^{n} {(-1)^{i+j} [A]_{i,j} \det {(A(i|j))}}.
$$
We will prove that $P(n)$ is true for $n = 1$, $2$, $3$, $\dots$ by mathematical induction.
$P(1)$ is true by definition.
It is easy to check that $P(2)$ is true (which I leave as an exercise).
Suppose that $P(m-1)$ is true. Our goal is to prove that $P(m)$ is true.
Let $A$ be an $m \times m$ matrix. Let $j$ be a positive integer less than or equal to $m$. If $j = 1$, it is just the definition. If $j > 1$, we first expand the determinant of $A$ about the first column, and then apply the hypothesis to every $(m - 1) \times (m - 1)$ submatrix:
$$
\begin{aligned}
& \det {(A)}
\\
= {} &
\sum_{i = 1}^{m} {
(-1)^{i+1} [A]_{i,1} \det {(A(i|1))}
}
\\
= {} &
\sum_{i = 1}^{m} {
(-1)^{i+1} [A]_{i,1}
\sum_{\substack{1 \leq \ell \leq m \\ \ell \neq i}} {
(-1)^{(\ell - \rho(\ell, i)) + (j - 1)}
[A]_{\ell,j} \det {(A({i,\ell}|{1,j}))}
}
}
\\
= {} &
\sum_{i = 1}^{m} {
\sum_{\substack{1 \leq \ell \leq m \\ \ell \neq i}} {
(-1)^{(\ell - \rho(\ell, i)) + (j - 1)}
(-1)^{i+1}
[A]_{i,1} [A]_{\ell,j} \det {(A({i,\ell}|{1,j}))}
}
}
\\
= {} &
\sum_{\ell = 1}^{m} {
\sum_{\substack{1 \leq i \leq m \\ i \neq \ell}} {
(-1)^{(\ell - \rho(\ell, i)) + (j - 1)}
(-1)^{i+1}
[A]_{i,1} [A]_{\ell,j} \det {(A({i,\ell}|{1,j}))}
}
}
\\
= {} &
\sum_{\ell = 1}^{m} {
\sum_{\substack{1 \leq i \leq m \\ i \neq \ell}} {
(-1)^{\ell} (-1)^{\rho(\ell, i)} (-1)^{i} (-1)^{j}
[A]_{i,1} [A]_{\ell,j} \det {(A({i,\ell}|{1,j}))}
}
}
\\
= {} &
\sum_{\ell = 1}^{m} {
\sum_{\substack{1 \leq i \leq m \\ i \neq \ell}} {
(-1)^{\ell + j} (-1)^{i - \rho(i, \ell) + 1}
[A]_{i,1} [A]_{\ell,j} \det {(A({i,\ell}|{1,j}))}
}
}
\\
= {} &
\sum_{\ell = 1}^{m} {(-1)^{\ell + j} [A]_{\ell,j}
\sum_{\substack{1 \leq i \leq m \\ i \neq \ell}} {
(-1)^{i - \rho(i, \ell) + 1}
[A]_{i,1} \det {(A({i,\ell}|{1,j}))}
}
}
\\
= {} &
\sum_{\ell = 1}^{m} {(-1)^{\ell + j} [A]_{\ell,j}
\det {(A(\ell|j))}
}.
\end{aligned}
$$
Here are two useful tips:
- $[A]_{\ell,j}$ is the $(\ell - \rho(\ell, i), j-1)$-entry of $A(i|1)$;
- $[A]_{i,1}$ is the $(i - \rho(i, \ell), 1)$-entry of $A(\ell|j)$.
Hence by mathematical induction, $P(n)$ is true for $n = 1$, $2$, $3$, $\dots$.
Proof of Theorem 2. Let the proposition $P(n)$ be as follows:
For any $n \times n$ matrix $A$ and for any positive integer $i$ less than or equal to $n$,
$$
\det {(A)} = \sum_{j = 1}^{n} {(-1)^{i+j} [A]_{i,j} \det {(A(i|j))}}.
$$
We will prove that $P(n)$ is true for $n = 1$, $2$, $3$, $\dots$ by mathematical induction.
$P(1)$ is true by definition.
It is easy to check that $P(2)$ is true (which I leave as an exercise).
Suppose that $P(m-1)$ is true. Our goal is to prove that $P(m)$ is true.
Let $A$ be an $m \times m$ matrix. Let $i$ be a positive integer less than or equal to $m$. We first expand the determinant of $A$ about the first column, and then apply the hypothesis to every $(m - 1) \times (m - 1)$ submatrix except $A(i|1)$ (in which we write $f = (-1)^{i+1} [A]_{i,1} \det {(A(i|1))}$ for brevity):
$$
\begin{aligned}
& \det {(A)}
\\
= {} &
f + \sum_{\substack{1 \leq k \leq m \\k \neq i}}
{(-1)^{k+1} [A]_{k,1} \det {(A(k|1))}}
\\
= {} &
f + \sum_{\substack{1 \leq k \leq m \\k \neq i}}
{(-1)^{k+1} [A]_{k,1}
\sum_{j = 2}^{m}
{(-1)^{i - \rho(i,k) + j - 1}
[A]_{i,j} \det {(A(k,i|1,j))}}}
\\
= {} &
f + \sum_{\substack{1 \leq k \leq m \\k \neq i}}
{\sum_{j = 2}^{m}
{(-1)^{k+1} [A]_{k,1}
(-1)^{i - \rho(i,k) + j - 1}
[A]_{i,j} \det {(A(k,i|1,j))}}}
\\
= {} &
f + \sum_{j = 2}^{m}
{\sum_{\substack{1 \leq k \leq m \\k \neq i}}
{(-1)^{k+1} [A]_{k,1}
(-1)^{i - \rho(i,k) + j - 1}
[A]_{i,j} \det {(A(k,i|1,j))}}}
\\
= {} &
f + \sum_{j = 2}^{m}
{\sum_{\substack{1 \leq k \leq m \\k \neq i}}
{(-1)^{i+j} [A]_{i,j}
(-1)^{k - \rho(k,i) + 1}
[A]_{k,1} \det {(A(k,i|1,j))}}}
\\
= {} &
f + \sum_{j = 2}^{m}
{(-1)^{i+j} [A]_{i,j}
\sum_{\substack{1 \leq k \leq m \\k \neq i}}
{(-1)^{k - \rho(k,i) + 1}
[A]_{k,1} \det {(A(k,i|1,j))}}}
\\
= {} &
f + \sum_{j = 2}^{m}
{(-1)^{i+j} [A]_{i,j} \det {(A(i|j))}}.
\end{aligned}
$$
Here are two useful tips (in which $k \neq i$ and $j \neq 1$):
- $[A]_{i,j}$ is the $(i - \rho(i, k), j-1)$-entry of $A(k|1)$;
- $[A]_{k,1}$ is the $(k - \rho(k, i), 1)$-entry of $A(i|j)$.
Hence by mathematical induction, $P(n)$ is true for $n = 1$, $2$, $3$, $\dots$.
It will be easier if it is first proved that the determinant of a square matrix can be computed by expansion about any row or column; see this for the details.
I will use the $\rho$-notation which is defined in the above answer.
I will prove only the first theorem; the proof of the second one is very similar to that of the first one, which I leave as an exercise.
Let the proposition $P(k)$ be as follows:
For any $n \times n$ matrix (in which $n \geq k$) and for any $k$ distinct integers $j_1$, $j_2$, $\dots$, $j_k$ less than or equal to $n$ (in which $j_1 < j_2 < \dots < j_k$),
$$
\begin{aligned}
\det {(A)}
= \sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n}
{\det {\left(
A\binom{i_1, i_2, \dots, i_k}
{j_1, j_2, \dots, j_k}
\right)}}
(-1)^{i_1 + i_2 + \dots + i_k
+ j_1 + j_2 + \dots + j_k}
\det {(A({i_1,i_2,\dots,i_k}|{j_1,j_2,\dots,j_k}))}.
\end{aligned}
$$
We will prove that $P(k)$ is true for $k = 1$, $2$, $3$, $\dots$.
$P(1)$ is true, because the determinant of a square matrix can be computed by expansion about any column.
Suppose that $P(k-1)$ is true. Our goal is to prove that $P(k)$ is true.
Let $A$ be an $n \times n$ matrix, with $n \geq k$. Let $j_1$, $j_2$, $\dots$, $j_k$ be any $k$ distinct integers less than or equal to $n$, with $j_1 < j_2 < \dots < j_k$. Then
$$
\begin{aligned}
& \det {(A)}
\\
= {} &
\sum_{d_1 = 1}^{n}
{[A]_{d_1,j_1}
(-1)^{d_1 + j_1}
\det {(A(d_1|j_1))}}
\\
= {} &
\sum_{d_1 = 1}^{n}
{[A]_{d_1,j_1}
(-1)^{d_1 + j_1}}
\sum_{\substack{
1 \leq d_2 < \dots < d_k \leq n \\
d_1 \neq d_2,\dots,d_k
}}
{\det {\left(
A\binom{d_2, \dots, d_k}{j_2, \dots, j_k}
\right)}}
(-1)^{d_2 - \rho(d_2, d_1) + \dots
+ d_k - \rho(d_k, d_1)
+ j_2 + \dots + j_k - (k - 1)}
\det
{(A({d_1,d_2,\dots,d_k}|{j_1,j_2,\dots,j_k}))}
\\
= {} &
\sum_{\substack{
1 \leq d_1 \leq n \\
1 \leq d_2 < \dots < d_k \leq n \\
d_1 \neq d_2,\dots,d_k
}}
{[A]_{d_1,j_1}
(-1)^{d_1 + j_1}}
{\det {\left(
A\binom{d_2, \dots, d_k}{j_2, \dots, j_k}
\right)}}
(-1)^{d_2 - \rho(d_2, d_1) + \dots
+ d_k - \rho(d_k, d_1)
+ j_2 + \dots + j_k - (k - 1)}
\det
{(A({d_1,d_2,\dots,d_k}|{j_1,j_2,\dots,j_k}))}
\\
= {} &
\sum_{\substack{
1 \leq d_1 \leq n \\
1 \leq d_2 < \dots < d_k \leq n \\
d_1 \neq d_2,\dots,d_k
}}
(-1)^{
(d_1 + \dots + d_k) + (j_1 + \dots + j_k)
+ (\rho(d_1, d_2) + \dots + \rho(d_1, d_k))
- 2(k-1)
}
[A]_{d_1,j_1}
{\det {\left(
A\binom{d_2, \dots, d_k}{j_2, \dots, j_k}
\right)}}
\det
{(A({d_1,d_2,\dots,d_k}|{j_1,j_2,\dots,j_k}))}
\\
= {} &
\sum_{\substack{
1 \leq d_1 \leq n \\
1 \leq d_2 < \dots < d_k \leq n \\
d_1 \neq d_2,\dots,d_k
}}
(-1)^{
(d_1 + \dots + d_k) + (j_1 + \dots + j_k)
+ (\rho(d_1, d_2) + \dots + \rho(d_1, d_k))
}
[A]_{d_1,j_1}
{\det {\left(
A\binom{d_2, \dots, d_k}{j_2, \dots, j_k}
\right)}}
\det
{(A({d_1,d_2,\dots,d_k}|{j_1,j_2,\dots,j_k}))}
\\
= {} &
\sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n}
\sum_{\substack{
1 \leq s \leq k\\
d_1 = i_s \\
d_r = i_{r-1}, \ 2 \leq r \leq s \\
d_r = i_{r}, \ r > s \\
}}
(-1)^{
(d_1 + \dots + d_k) + (j_1 + \dots + j_k)
+ (\rho(d_1, d_2) + \dots + \rho(d_1, d_k))
}
[A]_{d_1,j_1}
{\det {\left(
A\binom{d_2, \dots, d_k}{j_2, \dots, j_k}
\right)}}
\det
{(A({d_1,d_2,\dots,d_k}|{j_1,j_2,\dots,j_k}))}
\\
= {} &
\sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n}
\sum_{1 \leq s \leq k}
(-1)^{
(i_1 + \dots + i_k) + (j_1 + \dots + j_k)
+ (s-1)
}
[A]_{i_s,j_1}
{\det {\left(
A\binom{i_1,\dots,i_{s-1},i_{s+1},\dots,i_k}{j_2, \dots, j_k}
\right)}}
\det
{(A({i_1,i_2,\dots,i_k}|{j_1,j_2,\dots,j_k}))}
\\
= {} &
\sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n}
\left(
(-1)^{s-1}
\sum_{1 \leq s \leq k}
[A]_{i_s,j_1}
{\det {\left(
A\binom{i_1,\dots,i_{s-1},i_{s+1},\dots,i_k}{j_2, \dots, j_k}
\right)}}
\right)
(-1)^{
(i_1 + \dots + i_k) + (j_1 + \dots + j_k)
}
\det
{(A({i_1,i_2,\dots,i_k}|{j_1,j_2,\dots,j_k}))}
\\
= {} &
\sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n}
\left(
(-1)^{s+1}
\sum_{1 \leq s \leq k}
[A]_{i_s,j_1}
{\det {\left(
A\binom{i_1,\dots,i_{s-1},i_{s+1},\dots,i_k}{j_2, \dots, j_k}
\right)}}
\right)
(-1)^{
(i_1 + \dots + i_k) + (j_1 + \dots + j_k)
}
\det
{(A({i_1,i_2,\dots,i_k}|{j_1,j_2,\dots,j_k}))}
\\
= {} &
\sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n}
{
\det {\left(
A\binom{i_1, i_2, \dots, i_k}
{j_1, j_2, \dots, j_k}
\right)}
}
(-1)^{
(i_1 + \dots + i_k) + (j_1 + \dots + j_k)
}
\det
{(A({i_1,i_2,\dots,i_k}|{j_1,j_2,\dots,j_k}))}.
\end{aligned}
$$
We have used the hypothesis in the second equality.
Hence by mathematical induction, $P(k)$ is true for $k = 1$, $2$, $3$, $\dots$.
Note that the proof uses nothing more than the usual Laplace expansion.
Best Answer
This proof is direct, which is based on the fact that the determinant of a square matrix can be computed by expansion about any column.
I will prove that $P(n)$ (in the description of the question) is true for $n = 2$, $3$, $\dots$ by mathematical induction.
It is easy to check that $P(2)$ is true.
Suppose that $P(n-1)$ is true (in which $n \geq 3$). I will prove that $P(n)$ is true under the hypothesis.
Choose a positive integer $q$ less than or equal to $n$. Choose a positive integer $q$ less than $p$. Suppose that column $p$ of the $n \times n$ matrix $A$ is equal to column $q$ of $A$.
Choose a positive integer $u$ less than or equal to $n$ so that $u \neq p$ and that $u \neq q$. Note that $A(i|u)$ has two equal columns (for $i = 1$, $2$, $\dots$, $n$). By the hypothesis, $\det {(A(i|u))} = 0$. Hence $$ \begin{aligned} \det {(A)} = {} & \sum_{i = 1}^{n} {(-1)^{i+u} [A]_{i,u} \det {(A(i|u))}} \\ = {} & \sum_{i = 1}^{n} {(-1)^{i+u} [A]_{i,u} \,0} \\ = {} & 0. \end{aligned} $$
Hence by mathematical induction, $P(n)$ is true for $n = 2$, $3$, $\dots$.