3
$\begingroup$

Given an $n \times n$ square matrix $M$ in which every row and column contains exactly one $-1$ and one $1$, and is $0$ otherwise, I'm trying to calculate whether it's always possible to reach $-M$ through successive swapping of rows/columns.

I've worked out that it's at least possible sometimes, simply by trial-and-erroring arbitrary matrices by hand, but of course this is a long way from a proof, and it only proves that it's possible for those specific matrices. I'm not too sure where to start with this.

One thing I noticed is that if $\det(M) \neq 0$ then the number of swaps must match the evenness of $n$, because every swap will flip the sign of the determinant, and then we also have

$$\det(-M)=(-1)^n \det(M)$$

However I'm not sure if this is relevant at all, it's just the only thing I've managed to deduce so far.

Any pointers?

$\endgroup$
1
$\begingroup$

It is always possible to get $-M$ by the procedure below. But first, the determinant is always $0$, since a vector with all its coordinates equal will be in the kernel of $M$. So that argument will not take you far.

Now use row/column swaps to bring $M$ into a standard form. Note that the first row can always be transformed into $(1, -1, 0, \ldots)$. From here you can continue and get one of two options for the first two rows. Namely either $$\begin{pmatrix}1&-1&0&\ldots \\ -1&1&0&\ldots \end{pmatrix}$$ or $$\begin{pmatrix}1&-1&0&0&\ldots \\ 0&1&-1&0&\ldots \end{pmatrix}.$$ In the first case the new matrix $M’$ is in block diagonal form with a $2\times 2$ block in the upper left.

If the dimension of $M$ is greater than $2$ then use induction to argue that $M$ can indeed be transformed into $-M$.

So, using induction on the size $n$, the only case left is to consider an $m \times m$ matrix $M’$ for any $m\geq 2$ of the form $$M’ = \begin{pmatrix} 1 & -1 & 0 & \cdots & & 0 \\ 0 & 1 & -1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & & \vdots \\ 0 & \cdots & & & 1 & -1 \\ -1 & 0 & \cdots & & 0 & 1 \end{pmatrix}.$$

For this case, reversing the first $m-1$ rows (swap rows $1$ and $m-1$, rows $2$ and $m-2$, etc.) and then reversing all columns results in $-M’$.

Finally retrace the steps that transformed $M$ into $M’$ to get $-M$.

$\endgroup$

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.