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 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .