8

Related to the question link text I was asking myself some time ago the following. Can one precisely describe the invertible n\times n matrices with{0, 1} entries? For example, is anything special about the graph asociated to this matrix?

flag
I assume everything takes place over $\mathbb{R}$, here. – Martin Brandenburg Apr 7 2010 at 0:03
yes it should be invertible over \mathbb{R} – boolean number Apr 7 2010 at 13:49

2 Answers

5

You are unlikely to find a characterization which does not result from simple facts in linear algebra. I am unaware of any characterizations which make interesting statements about graphs.

You may want to choose the ring over which the matrices belong. For example, the same matrix may be invertible over the reals, but if it has even determinant, then it is not invertible over the field of two elements. You can say that, given a matrix A, the parallelipiped associated with the rows (or columns) of A is nontrivial (has nonzero volume in R^n) iff the matrix is invertible over the reals, but this is a simple consequence of a geometric interpretation of determinant; it doesn't give anything new. Also, the eigenvalues of the adjacency matrix of a directed graph are all nonzero precisely when said matrix is invertible over the reals; big hairy tautological deal, as I am just saying a matrix is invertible when its determinant is nonzero.

Consider the ring above fixed, and look at the {0,1}-matrices over that ring which are invertible. This set includes some lower triangular matrices, some upper triangular matrices, some "comb matrices" where you take an invertible matrix and alternately add an extra row and column, picking one of them to be mostly zeros and the other mostly 1's, while making the diagonal all 1's, and alternating between rows and columns. In addition to these patterns, you have some block matrices, incidence geometries, certain combinatorial designs, and so on, all belonging to the class of invertible {0,1}- matrices, and looking pretty woolly as a set. The attendant directed graphs will be a similarly woolly-looking set of graphs.

Given the above, it may be possible to describe the class of graphs in an interesting way. For example, if you build the matrices by augmentation, consider the corresponding operation for adding a vertex and certain edges to a graph. You may be able to prove facts about the set of graphs so constructed, especially as a set of representatives of isomorphism classes of graphs. I just don't think the result will look pretty, appealing, or useful without a major shift in perspective.

Gerhard "Ask Me About System Design" Paseman, 2010.04.06

link|flag
Thanks a lot for your answer! Can you give a reference regarding the augmentation process you mentioned in the last paragraph of your answer? A non trivial characterization, not in terms of the directed graph will also be helpful. I am more interested in the boolean algebra associated to this matrix. Is anything known about it? – boolean number Apr 7 2010 at 13:59
1 
 Take an nxn matrix A. Augmenting A means making an (n+1)x(n+1) matrix B with A as a minor, usually by adding a row at the bottom and a column on the right. I use it in a proof sketch given at grpmath.prado.com/Lemmas.html . For graphs, it would mean adding a vertex and certain directed edges to a graph. I do not know which boolean algebra you are associating with the matrix. Perhaps that will be a separate Math Overflow question? Gerhard "Ask Me About System Design" Paseman, 2010.04.08 – Gerhard Paseman Apr 7 2010 at 17:00
Let X=\{1,2,\cdots ,n\} and A a matrix with \{0, 1\} entries. Each row of A can be regarded as a subset of X just by taking into acoount only the `1`-entries from that row. Then one can consider the subalgebra of \mathcal{P}(X) generated by the rows of A. The operations on \mathcal{P}(X) are intersection and symmetric difference. – boolean number Apr 8 2010 at 11:45
It is not hard to prove that all the minimal elements of this subalgebra have cardinality one. But this is not a enough to draw the conclusion that A is invertible. So the question I am asking is if one can give an equivalent condition of invertibility only in terms of this subalgebra of \mathcal{P}(X)? I don't know if this deserves as a separate question on MO. – boolean number Apr 8 2010 at 11:46
A isa n\times n matrix. I forgot to mention in the first comment. – boolean number Apr 8 2010 at 11:51
show 1 more comment
2

At least for symmetric matrices, such graphs have been studied under the name singular graphs. See, for instance, this paper.

link|flag

Your Answer

Get an OpenID
or

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