Why does Bondy's Theorem work?

Bondy's theorem says that any $n$ by $n$ matrix with distinct rows can have one column removed from it to produce a new matrix where all the rows are still distinct. In easy terms, how does he know this?

• One version I found assumed the matrix had all entries 0 or 1. Do you know the result holds for any matrix, or maybe you forgot to mention the 0,1 entries constraint? – coffeemath Oct 21 '15 at 12:20
• I do know that the result holds for any matrix, but I would accept an answer for the zeros and ones case as well. – Everyone_Else Oct 21 '15 at 12:21
• Someone-- I haven't thought about it, but it may be that the 0,1 case is equivalent to the general case anyway. – coffeemath Oct 21 '15 at 12:36
• @coffeemath At first it seemed immediately equivalent to me, but then I lost my certainty. – Matt Samuel Oct 21 '15 at 13:00
• @MattSamuel I also don't see (now) how to get from the 0,1 result to the general result. I thought of saying there are two distinct entries a,b then replacing all a's by 1 and all non-a's by 0. But then a deletion of a zero column might not correspond to rows of given matrix distinct... – coffeemath Oct 21 '15 at 14:05

This is an attempt to explain in simple terms Bondy's original proof.

Let's say that a column "links" rows $i$ and $j$ if, when you remove it, these rows become identical. And say that a column is "active" if it links at least one pair of rows (more than one is certainly possible).

Then what we want to do is to prove that there's a non-active column. If there is one, that's the one we remove. We will prove this by proving that the number of active columns is $< n$.

Using column links, you can jump from row to row, always jumping to a row which differs just in one column from where you come. Two rows are connected if you can get from one to another with such jumps. This way you can visualize rows as vertices in a graph, and all the vertices break up into disjoint connected components. The edges connecting the vertices are column links, but we should remember that the same column may participate more than once as a link (even in different connected components). We certainly have no. of active columns $<=$ no. of links, however.

Suppose now that in each connected component there are no cycles - that is, you can't start from one row, jump around and return to it and not use the same link twice. That means that each component is a tree, and a tree always has fewer edges than vertices (in fact, $m-1$ edges for $m$ vertices). So then summing over all components we get no. of links $<$ no. of vertices $= n$, and therefore the no. of active columns is also $<n$, as desired.

But maybe some components have cycles. In a cycle, you jump from one row to another using a bunch of column links and return to where you started. You don't use the same link twice, but you certainly have to use the same column twice: for example, if you modified column $i$ in the first jump, eventually you have to modify column $i$ again to get back; it'll be a different link (between different rows), but the same column. So look at any cycle, and take two links from it that are the same underlying column, and delete one of them from the graph. This will break the cycle and decrease the number of edges by $1$, but it will not lose an active column, because the second link with the same column stays. Keep doing this until there are no cycles left. Then the previous paragraph applies and finishes the proof.

A completely different and possibly more intuitive geometric approach.

Rows of the matrix determine points in $R^n$. Rows are distinct - points are distinct. Suppose that after deleting the $i$-th column two rows become the same - that means that the line between the two corresponding points is parallel to the $i$-th basis vector.

So if deleting every column makes some two rows the same, that means there are $n$ pairwise orthogonal lines among those that connect pairs of points.

But any $n$ points lie inside an $(n-1)$-dimensional subspace (affine, not linear; doesn't have to go through $0$). That subspace cannot contain $n$ pairwise orthogonal nonzero vectors.