Author |
Topic: Singular (0, 1) matrices (Read 1146 times) |
|
wasteland
Newbie
Posts: 3
|
 |
Singular (0, 1) matrices
« on: Nov 12th, 2004, 2:05am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Singular (0, 1) matrices
« Reply #1 on: Nov 12th, 2004, 3:40am » |
Quote Modify
|
If you want just any condition: if all elements are 0, then the determinant is 0. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wasteland
Newbie
Posts: 3
|
|
Re: Singular (0, 1) matrices
« Reply #2 on: Nov 12th, 2004, 9:36am » |
Quote Modify
|
Ha ha  ... a _necessary_ and sufficient condition, please.
And please, not this one: "The determinant must be zero" (or those of its ilk)  .
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Singular (0, 1) matrices
« Reply #3 on: Nov 13th, 2004, 11:51pm » |
Quote Modify
|
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. View the PS format for better quality. The relevant part is section 3.1.
Singular 0/1 Matrices etc.
Sloane’s Integer Sequence 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.
|
| « Last Edit: Nov 13th, 2004, 11:55pm by Barukh » |
IP Logged |
|
|
|
wasteland
Newbie
Posts: 3
|
|
Re: Singular (0, 1) matrices
« Reply #4 on: Nov 17th, 2004, 8:50am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
madhurt
Newbie
Gender:
Posts: 1
|
|
Re: Singular (0, 1) matrices
« Reply #5 on: Nov 17th, 2004, 3:55pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Singular (0, 1) matrices
« Reply #6 on: Nov 17th, 2004, 4:18pm » |
Quote Modify
|
on Nov 17th, 2004, 3:55pm, 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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Singular (0, 1) matrices
« Reply #7 on: Nov 17th, 2004, 11:51pm » |
Quote Modify
|
on Nov 17th, 2004, 3:55pm, 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?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Singular (0, 1) matrices
« Reply #8 on: Nov 18th, 2004, 10:55am » |
Quote Modify
|
on Nov 17th, 2004, 11:51pm, 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 r1, r2, .., rn and c1, c2, ..., cn).
ri is connected to cj iff the ijth = (aij) entry of the matrux is 1.
A perfect matching corresponds to a permutation [pi] such that the product a1[pi](1)a2[pi](2)...an[pi](n) is non-zero.
|
| « Last Edit: Nov 18th, 2004, 10:57am by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print