MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 edited formulas in proof using (D), for I've made a mistake previously.

Here are two more conditions.

(D) Find $n - 1$ such vectors (of size $N$ each) that $n$ rows or columns of your matrix are linear combinations of these vectors.

This is more general than (B), because if you know (B) then you can choose all but one of those rows or columns as your vectors. However, (B) is not more general than (D) because to go from (D) to (B) you have to invert a matrix of size $n$, where $n$ can be as large as $N$, which is as difficult as computing the original determinant in first place.

If $n = N$, this condition actually says that a matrix has determinant zero if it's the product of an $N \times (N-1)$ matrix with an $(N-1) \times N$ matrix.

(E) The sum of the $N!$ expansion terms of the determinant is zero.

This comes up less often than the others, but it is a way.

Let me illustrate these conditions with an example where three of the conditions can be used.

Suppose $\mathbf{u}_1, \dots \mathbf{u}_N$ and $\mathbf{v}_1, \dots \mathbf{v}_N$ are real vectors in $\mathbb{R}^{N-1}$. Let $A$ be the $N \times N$ matrix whose element $a_{i,j}$ is the dot product $\langle \mathbf{u}_i|\mathbf{v}_j\rangle$. We want to prove that $\det A = 0$.

The easiest way to prove this is using the condition (D). Let's take a basis $(\mathbf{e}_1, \dots, \mathbf{e}_{N-1})$ of the vector space, and write the vectors in this basis as $\mathbf{u}_i = \sum_k u_{i,k} \mathbf{e}_k$ and $\mathbf{v}_j = \sum_k v_{j,k} \mathbf{e}_k$. A general element of the matrix can be written as $a_{i,j} = \langle\mathbf{u}_i|\mathbf{v}_j\rangle = \sum_k u_{i,k} v_{j,k}$. This means that any row $\mathbf{a}_i = (a_{i,1}, \dots, a_{i,N})$ is a linear combination of the vectors $\mathbf{v}_1, mathbf{w}_1, \dots, \mathbf{v}_{N-1} mathbf{w}_{N-1}$ where $\mathbf{w}_k = (v_{1,k}, \dots, v_{N,k})$, namely $\mathbf{a}_i = u_{i,1} \mathbf{v}_1 mathbf{w}_1 + \dots u_{i,N-1} \mathbf{v}_{N-1} mathbf{w}_{N-1}$.

You can use condition (B) in a similar way. For this you must first find a linear dependence among the vectors $\mathbf{u}_1, \dots, \mathbf{u}_N$. Such a dependence must exist because these are $N$ vectors in an $N - 1$ dimensional space. So suppose $\mathbf{0} = \lambda_1 \mathbf{u}_1 + \dots + \lambda_N \mathbf{u}_N$ where not all coefficients are zero. Now $\sum_i \lambda_i a_{i,j} = \sum_i \langle\mathbf{u}_i|\mathbf{v}_j\rangle =$ $\bigl\langle \bigl(sum_i\mathbf{u}_i\bigr)\bigm|\mathbf{v}_j\rangle = \langle\mathbf{0}|\mathbf{v}_j\rangle = 0$, which means the rows of the matrix are linear dependent.

There is also a way to use condition (E) to give a proof. This proof is complicated compared to the others but has a special place in my heart.

For this, again consider the coordinates of the vectors and write the elements of the matrix in the form $a_{i,j} = \sum_k u_{i,k} v_{j,k}$. If you now expand the determinant and completely, you find that the determinant can be written as the huge sum

$$\det A = \sum_j \sum_k (-1)^j \prod_i u_{i,k_i} v_{j_i,k_i}$$

where $j : (\{1\dots N\} \to \{1\dots N\})$ goes over all permutations and $k : (\{1\dots N\} \to \{1\dots N-1\})$ over all sequences.

Any such vector $k$ must have a repetition, because the range is smaller than the domain. Let thus $k_r = k_s$ where $r < s$ are indices, and have $(r, s)$ be the least pair of indices where such a repetition is true (use any total ordering of pairs). Now define $j'$ as the permutation such that $j'(r) = j(s)$, $j'(s) = j(r)$, but $j'$ is equal to $j$ in all other places. For any given $k$, this breaks the permutations into disjoint pairs $\{j, j'\}$. Notice now that

$$\prod_i u_{i,k_i} v_{j_i,k_i} = \prod_i u_{i,k_i} v_{j'_i,k_i}$$

but the signs of the permutation are opposite so $(-1)^{j'} = -(-1)^j$. This implies the terms in that sum come in pairs that exactly cancel out each other, so indeed the determinant is zero.

Update: edited formulas in proof using (D), for I've made a mistake previously.

1

Here are two more conditions.

(D) Find $n - 1$ such vectors (of size $N$ each) that $n$ rows or columns of your matrix are linear combinations of these vectors.

This is more general than (B), because if you know (B) then you can choose all but one of those rows or columns as your vectors. However, (B) is not more general than (D) because to go from (D) to (B) you have to invert a matrix of size $n$, where $n$ can be as large as $N$, which is as difficult as computing the original determinant in first place.

If $n = N$, this condition actually says that a matrix has determinant zero if it's the product of an $N \times (N-1)$ matrix with an $(N-1) \times N$ matrix.

(E) The sum of the $N!$ expansion terms of the determinant is zero.

This comes up less often than the others, but it is a way.

Let me illustrate these conditions with an example where three of the conditions can be used.

Suppose $\mathbf{u}_1, \dots \mathbf{u}_N$ and $\mathbf{v}_1, \dots \mathbf{v}_N$ are real vectors in $\mathbb{R}^{N-1}$. Let $A$ be the $N \times N$ matrix whose element $a_{i,j}$ is the dot product $\langle \mathbf{u}_i|\mathbf{v}_j\rangle$. We want to prove that $\det A = 0$.

The easiest way to prove this is using the condition (D). Let's take a basis $(\mathbf{e}_1, \dots, \mathbf{e}_{N-1})$ of the vector space, and write the vectors in this basis as $\mathbf{u}_i = \sum_k u_{i,k} \mathbf{e}_k$ and $\mathbf{v}_j = \sum_k v_{j,k} \mathbf{e}_k$. A general element of the matrix can be written as $a_{i,j} = \langle\mathbf{u}_i|\mathbf{v}_j\rangle = \sum_k u_{i,k} v_{j,k}$. This means that any row $\mathbf{a}_i = (a_{i,1}, \dots, a_{i,N})$ is a linear combination of the vectors $\mathbf{v}_1, \dots, \mathbf{v}_{N-1}$, namely $\mathbf{a}_i = u_{i,1} \mathbf{v}_1 + \dots u_{i,N-1} \mathbf{v}_{N-1}$.

You can use condition (B) in a similar way. For this you must first find a linear dependence among the vectors $\mathbf{u}_1, \dots, \mathbf{u}_N$. Such a dependence must exist because these are $N$ vectors in an $N - 1$ dimensional space. So suppose $\mathbf{0} = \lambda_1 \mathbf{u}_1 + \dots + \lambda_N \mathbf{u}_N$ where not all coefficients are zero. Now $\sum_i \lambda_i a_{i,j} = \sum_i \langle\mathbf{u}_i|\mathbf{v}_j\rangle =$ $\bigl\langle \bigl(sum_i\mathbf{u}_i\bigr)\bigm|\mathbf{v}_j\rangle = \langle\mathbf{0}|\mathbf{v}_j\rangle = 0$, which means the rows of the matrix are linear dependent.

There is also a way to use condition (E) to give a proof. This proof is complicated compared to the others but has a special place in my heart.

For this, again consider the coordinates of the vectors and write the elements of the matrix in the form $a_{i,j} = \sum_k u_{i,k} v_{j,k}$. If you now expand the determinant and completely, you find that the determinant can be written as the huge sum

$$\det A = \sum_j \sum_k (-1)^j \prod_i u_{i,k_i} v_{j_i,k_i}$$

where $j : (\{1\dots N\} \to \{1\dots N\})$ goes over all permutations and $k : (\{1\dots N\} \to \{1\dots N-1\})$ over all sequences.

Any such vector $k$ must have a repetition, because the range is smaller than the domain. Let thus $k_r = k_s$ where $r < s$ are indices, and have $(r, s)$ be the least pair of indices where such a repetition is true (use any total ordering of pairs). Now define $j'$ as the permutation such that $j'(r) = j(s)$, $j'(s) = j(r)$, but $j'$ is equal to $j$ in all other places. For any given $k$, this breaks the permutations into disjoint pairs $\{j, j'\}$. Notice now that

$$\prod_i u_{i,k_i} v_{j_i,k_i} = \prod_i u_{i,k_i} v_{j'_i,k_i}$$

but the signs of the permutation are opposite so $(-1)^{j'} = -(-1)^j$. This implies the terms in that sum come in pairs that exactly cancel out each other, so indeed the determinant is zero.