wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Singular (0, 1) matrices
        
(Message started by: wasteland on Nov 12^th, 2004, 2:05am)

Title: Singular (0, 1) matrices
Post by wasteland on Nov 12^th, 2004, 2:05am

Does anybody know some condition for a (0, 1) square matrix (one whose entries are 0 or 1 only) to be singular (i.e. to have zero determinant)? I believe Williamson had a 1946 paper in the Amer. Math. Monthly on this subject... does anybody have a copy of this paper?

Title: Re: Singular (0, 1) matrices
Post by towr on Nov 12^th, 2004, 3:40am

If you want just any condition: if all elements are 0, then the determinant is 0. ::)

Title: Re: Singular (0, 1) matrices
Post by wasteland on Nov 12^th, 2004, 9:36am

Ha ha :)... a _necessary_ and sufficient condition, please.

And please, not this one: "The determinant must be zero" (or those of its ilk) ;D.

Title: Re: Singular (0, 1) matrices
Post by Barukh on Nov 13^th, 2004, 11:51pm

wasteland, are you sure such conditions were stated in any satisfactory way? The reason I am asking is this: it seems that 0/1 singular matrices draw a significant attention in relation to other structures (i.e. polytopes), but the best it can be done today is roughly estimate the probability that a random 0/1 matrix is singular. Were the conditions of the singularity stated clearly, I would expect much more progress on that.

Anyway, here’re a few links to consider:

Lectures on 0/1-Polytopes (http://citeseer.ist.psu.edu/ziegler99lecture.html
). View the PS format for better quality. The relevant part is section 3.1.

Singular 0/1 Matrices etc. (http://arxiv.org/PS_cache/math/pdf/0308/0308050.pdf)

Sloane’s Integer Sequence A046747 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A046747), with additional links.

It seems Gunter M. Ziegler is an expert in the field. Maybe, you can contact him by e-mail and obtain more information.

Title: Re: Singular (0, 1) matrices
Post by wasteland on Nov 17^th, 2004, 8:50am

Thanks Barukh, that gives us a lot of food for thought. The characterization is actually necessary for a related problem in graph theory -- which is being tackled by a friend, not me, so I was just doing some proxy posting. Perhaps he'll expound more on exactly what he's trying to do later.

Title: Re: Singular (0, 1) matrices
Post by madhurt on Nov 17^th, 2004, 3:55pm

Hello!! Actually I am "the friend" mentioned in wasteland's mail and am new to this forum. Not too much work seems to have been done on this problem. The only references I could find were from 1946, 1957 and 1967. Also, the 67 refernce says that the enumeration problem is unsolved and only deals with a subclass of such matrices.

Let me state the problem a bit more clearly. Each square (0,1) matrix can denote a bipartite graph with equal number of vertices on both sides. Now, the singularity condition amounts to saying that the number of perfect matchings in the graph with odd and even parity are equal. The question is - what kind of structural constraints does it impose on the graph?

Title: Re: Singular (0, 1) matrices
Post by Aryabhatta on Nov 17^th, 2004, 4:18pm

on 11/17/04 at 15:55:43, madhurt wrote:

Let me state the problem a bit more clearly. Each square (0,1) matrix can denote a bipartite graph with equal number of vertices on both sides.

Ok. Thats right.

Quote:

Now, the singularity condition amounts to saying that the number of perfect matchings in the graph with odd and even parity are equal.

Lost you here.

Did you mean: "The number of perfect matchings is even" ?

If we consider the permutation expansion of the determinant of the matrix, each non-zero term corresponds to a perfect matching in the graph. Determinant (over F_2) is zero implies that the number of such terms must be even, i.e the number of perfect matchings is even.

Maybe a book on algebraic/spectral graph theory will provide insight into the structure of the graph.

Title: Re: Singular (0, 1) matrices
Post by Barukh on Nov 17^th, 2004, 11:51pm

on 11/17/04 at 15:55:43, madhurt wrote:

The only references I could find were from 1946, 1957 and 1967.

I was in the library the other day and looked at the Williamson’s paper from 1946. It doesn’t consider the matrices with 0-determinant. What it does is to get the bounds of the maximal possible value of the determinant of 0/1 matrix.

Quote:

Each square (0,1) matrix can denote a bipartite graph with equal number of vertices on both sides.

Do you mean the incidence matrix where rows represent one set, and columns – another? Doesn’t that imply that the matrix is symmetric w.r.t. the main diagonal?

Title: Re: Singular (0, 1) matrices
Post by Aryabhatta on Nov 18^th, 2004, 10:55am

on 11/17/04 at 23:51:36, Barukh wrote:

Do you mean the incidence matrix where rows represent one set, and columns – another? Doesn’t that imply that the matrix is symmetric w.r.t. the main diagonal?

I think he meant the following:

Given an nxn matrix (need not be symmetric), draw a bipartite graph as follows.

The vertex set of the graph is V = R U C such that the edges are only between R and C, and for each row in the matrix, we have exactly one vertex in R and for each column we have exactly one vertex in C. (say r₁, r₂, .., r_n and c₁, c₂, ..., c_n).

r_i is connected to c_j iff the ij^th = (a_ij) entry of the matrux is 1.

A perfect matching corresponds to a permutation [pi] such that the product a_1[pi](1)a_2[pi](2)...a_n[pi](n) is non-zero.