Assume that we have an anti-symmetric matrix that consists of 1's and -1's and 0's. All the elements of the main diagonal are 0 and each row and each column has exactly one 1, and one -1. Design an algorithm that replaces all 1's with -1's and vice versa only by swapping some rows and some columns.
Your matrix encodes a directed graph in which the in-degree and out-degree of each vertex is 1. In other words, your graph is a collection of directed cycles.
If you swap rows $i$ and $j$ and columns $i$ and $j$, then you have swapped vertices $i$ and $j$ in the graph. This has the effect of switching the direction of the edge between $i$ and $j$, but also affects other edges touching $i$ and $j$.
In order to finish the solution, it suffices to consider a single directed cycle involving all vertices, say $1 \to 2 \to \cdots \to n \to 1$. We would like to swap vertices so that the the cycle becomes $1 \gets 2 \gets \cdots \gets n \gets 1$.
We now consider two cases:
- $n = 2k+1$ is odd. In this case, we swap $(1,n), (2,n-1), \ldots, (k,k+2)$ to get $$ n \to n-1 \to \cdots \to k+2 \to k+1 \to k \to \cdots \to 1 \to n. $$
- $n = 2k$ is even. In this case, we swap $(1,n), (2,n-1), \ldots,(k,k+1)$ to get $$ n \to n-1 \to \cdots \to k+1 \to k \to \cdots \to 1 \to n. $$