Existence of a binary symmetric matrix from row sums

Give a sequence of column/row sums, is it possible to determine (other than by brute force) whether there exists a binary, symmetric matrix with the same column/row sums?

I did find the following article,

but my math skills aren't good enough to extract what I'm looking for or really determine 100% that this is what I'm talking about.

• I take it that by "binary" you mean the entries are all zeros and ones. If you drop the word, "symmetric", there is a thorough discussion in Chapter 6 of Ryser, Combinatorial Mathematics, which is Number 14 in the Carus Mathematical Monographs series published by the Mathematical Association of America. The books in that series are expository in nature. Maybe you can adapt the methods in that chapter to the special case of symmetric matrices. Commented Apr 25, 2012 at 22:47
• Thanks for the references, I did mean 1/0s. I guess an equivalent problem would be finding whether a undirected graph exists given vertex degrees
– dfb
Commented Apr 26, 2012 at 0:23
• It's equivalent if you allow your graphs to have loops, that is, edges joining a vertex to itself. Commented Apr 26, 2012 at 1:16
• I think it has certain relations with LONESUM matrices.
– hkju
Commented Apr 26, 2012 at 6:07
• LONESUM MATRICES are the matrices avoiding the $2 \times 2$ submatrix of the types [[1,0],[0,1]] or [[0,1],[1,0]].
– hkju
Commented Apr 26, 2012 at 6:14

Hakimi (1962) proved that $(d_1, d_2, ..., d_n)$ is a degree sequence of a simple graph if and only if $(d_2 − 1, d_3 − 1, ..., d_{d_1+1} − 1, d_{d_1+2}, > d_{d_1+3}, ..., d_n)$ is. This fact leads to a simple algorithm for finding a simple graph that has a given realizable degree sequence:
• What is dd1+1-1? Is that $d_{d_1+1}-1$? Commented Apr 26, 2012 at 1:14