Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The two most elementary ways to prove an N x N matrix's determinant = 0 are:

A) Find a row or column that equals the 0 vector.

B) Find a linear combination of rows or columns that equals the 0 vector.

A can be generalized to

C) Find a j x k submatrix, with j + k > N, all of whose entries are 0.

My minor question is: Is C a named theorem that one can easily reference?

My major question is: Are there are other canonical ways of proving a determinant = 0?

The context is that I'm trying to solve the generalized form of what was, as stated, a very easy Putnam Exam problem, and I last took a linear algebra class in 1974.

In response to comments below, let me say: - Thanks! - This isn't about computational efficiency. - Frobenius-Koenig looks very helpful.

share|improve this question
2  
The answer to your minor question is the Frobenius-König theorem. –  Erick Wong Jan 13 '13 at 8:47
2  
how about calculating the determinant? it's an $O(N^3)$ operation, so any alternative would have to be more efficient –  Carlo Beenakker Jan 13 '13 at 11:02
1  
@EricWong: Or, rather, the determinantal Frobenius-Konig theorem (the original deals with the permanent). –  Felix Goldberg Jan 13 '13 at 11:32
2  
I'm not sure (C) deserves a name. It's a trivial consequence of the definition of a determinant as a sum over the symmetric group (and the pigeonhole principle, if you like): all $n!$ terms in the sum are zero. –  user30035 Jan 13 '13 at 12:06
2  
Frobenius-Koenig looks like what I need. Thanks! –  Curt Monash Jan 15 '13 at 1:54

4 Answers 4

The Lindstrom-Gessel-Viennot Lemma is sometimes useful if you can find a nice enough graph corresponding to your matrix. I guess I wouldn't call this canonical though.

Edit: Well, I don't totally understand the downvote. To illustrate with a nice example (which I think is in the original Gessel-Viennot paper), if one takes $A$ to be the $n\times n$ matrix with $[A]_{i,j}={i+j-2\choose i-1}$, then the lemma provides a very elegant way to prove that the determinant of this matrix is 1, and if we then subtract $1$ from the $(n,n)$-entry, then the determinant is 0.

share|improve this answer
    
(ok downvote got cancelled out by somebody...thanks!) –  Casteels Jan 14 '13 at 21:20
    
The Lemma is very nice. Thanks for the pointer. But how do you manage to find an easy (directed and weighted) graph representing a given matrix? I know you don't claimed this to be feasible but are some considerations? I can imagine there is a generic algorithm which allows to "rediscover" Leibniz' formula. –  Stephan Müller Jan 15 '13 at 11:28
    
Well I think Leibniz' formula is essentially recovered from considering a complete bipartite graph (although note that one uses the formula to prove the lemma). But yeah, for an arbitrary matrix, I'm not sure how useful the LGV Lemma will be. The question stated that he was trying to generalize a Putnam problem, so I thought his matrix entries might be counting something, which is when the lemma can sometimes come in handy. –  Casteels Jan 15 '13 at 16:35

I tend to think a matrix is a linear transformation from a vector space to another vector space. From Linear algebra, we know that a linear transformation $T: V \to W$ has property:

$$ dim(R(T)) + dim(N(T)) = dim(V) $$

where $R(T) = \{ T(x): x \in V \}$, $N(T) = \{ x \in V: T(x) = 0 \}$

Determinant is found from the concept of the area of the parallelogram in 2-dimensional space.

Let $M$ be a n-dimensional matrix over $\mathbb{R}$ In order to have determinant zero, i.e. the n-parallelotope pointed by $T(v)$ should has zero volume in $\mathbb{R}^n$. To have zero volume, the linear transformation associated with matrix $M$ should map the whole vector space into a range that has dimension strictly lower than $n$.

A and B method is same as proving $N(T) \neq \{0\}$

share|improve this answer

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{w}_1, \dots, \mathbf{w}_{N-1} $ where $ \mathbf{w}_k = (v_{1,k}, \dots, v_{N,k}) $, namely $ \mathbf{a}_i = u_{i,1} \mathbf{w}_1 + \dots u_{i,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.

share|improve this answer

To answer your minor question, it might be referred as a calculation of Laplace expansion of a determinant.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.