Skip to main content
1 of 1
Post Made Community Wiki

I will take this opportunity to post my favorite linear algebra problem. I call it 0 not equal to 1.

Let A be an nxn 0-1 matrix with nonzero determinant. Show that there is a 1 in every row and in every column of A, and further there is a permutation matrix P so that PA has a diagonal of all 1's.

Let B be an nxn 0-1 matrix with nonzero determinant. We cannot show that there is a 0 in every row and in every column, so assume B also has this property. Are there nxn permutation matrices P and Q such that PBQ has all 0's on the diagonal? If not, how small a trace can one guarantee?

Gerhard "Ask Me About System Design" Paseman, 2012.03.03