An $n$-dimensional square matrix $A$ is a $(0,1)$-matrix if $A_{ij} \in \{0,1\}$ for each $i,j \in [n]$. An $n \times n$ $(0,1)$-matrix is complete if the diagonal entries are all $1$ i.e., $A_{jj} = 1$ for all $j \in [n]$.
A row swap of a matrix is simply swapping any two of its rows. A column swap is defined similarly. Lastly, we say a square $(0,1)$-matrix $A$ is almost-complete if there exists a (finite) sequence of row/column swaps which transforms $A$ into a complete matrix $A'$.
Now, consider the following computational problem.
(Problem 1) We require a polytime algorithm which, given a square $(0,1)$-matrix $A$, decides whether or not it is almost-complete.
It may be worth noting that a solution does indeed exist (at least according to the person who posed this problem to me). The hint I was given is that this is a (graph) matching problem in disguise, but somehow I can't map row or column swaps to something having to do with a graph. I would imagine that the matrix $A$ could be interpreted as an adjacency matrix.
I feel as though there should be some purely linear algebra based algorithm which works here, given that the determinant is preserved under row and column swaps, up to a factor of $-1$.
Another hypothesis (which again I can't prove) is that any $(0,1)$ square matrix $A$ with nonzero determinant is almost-complete (obviously, the converse is false).
(Problem 2) Is there a straightforward mathematical characterization of almost-complete $(0,1)$-matrices?
(Problem 2):
Claim: $A$ is almost complete if and only if you can put $n$ rocks on entries numbered $1$ such that they don't attack each other.
Proof: note that row and column swapping operation doesn't change whether the rocks can attack each other or not. In the end of all the swaps, the rocks are on the diagonal, so they can't attack each other. Hence originally they can't.
(Problem 1):
Make a graph with $n$ vertices for $n$ column and another $n$ vertices for $n$ row. Then put an edge between a column vertex and a row vertex if the entries for them is an $1$. The problem now reduce to a graph matching problem (EDIT: easily see that this is a bipartite graph, which has easier matching problem).