Number of symmetric square matrices with 0/1 such that all rows and all cols contain at least one 1 Symmetric meaning the main diagonal, i.e., matrix[i][j] = matrix[j][i].
Examples: identity matrix; matrix filled with 1s; matrix where the first row and first col are all 1s
I am stuck because I can't find a good way to take into account the symmetric condition. I tried to simplify the problem into just the lower-left half, but I don't think that's possible. I also tried to think of a recursive approach, which works for the easier version of the problem without the symmetric condition, but I can't get it to work here.
 A: One recursive formula is to add one row at a time.  So find the number $f(m,n)$ of all $m \times n$ matrices with entries in $\{0,1\}$ and $m \leq n$ such that the first $m$ columns form a symmetric matrix and each row contains at least one $1$.  Let $f(0,n)=1$ for convenience, then $f$ satisfies the following recursion: $$f(m+1,n)=2^{n-m} f(m,n) - f(m,n-1).$$
This follows from the fact that the first $m$ entries of row $m+1$ are fixed by symmetry.  This leaves $2^{n-m}$ options for the rest of the row if we allow a row of all zeroes.  A row of all zeroes means that column $m+1$ of the $m\times n$ matrix must be all zeroes. So this column does not contribute any $1$ so there are $f(m, n-1)$ of such matrices.  This is the correction term that is subtracted in the recursion above.
The sequence $f(n,n)$ starts with (counting from $n=0$) $$1, 1, 5, 45, 809, \ldots$$ and matches sequence A322661 of the OEIS.  Indeed, the formulation there in terms of number of graphs is equivalent with the definition here: How many graphs with numbered vertices exist in which self-edges (loops) are allowed and in which each vertex has at least one edge connected to it.
