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.

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

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:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.