linear algebra - Characterizing invertible matrices with {0,1} entries

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