# Replace 1's with -1's and vice versa in a matix

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.

• What have you tried? Where did you get stuck? Can you solve this for 2x2 matrices? 3x3? 4x4? 5x5? – Yuval Filmus Dec 31 '18 at 8:27
• @YuvalFilmus I can solve it for 2*2 or 3*3 but I can't find a general solution for n*n – mohammad mozafari Dec 31 '18 at 8:31

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$$.
1. $$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.$$
2. $$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.$$