Given a matrix $m\in\{-1,+1\}^{n\times n}$. Consider $m^\sigma$ to be collection of all matrices obtained from $m$ by permuting rows and columns.

Consider $\mathscr{M}[m^\sigma]$ to be collection of all $n\times n$ matrices obtained from matrices in $m^\sigma$ by swapping an equal number of rows for an equal number of columns of same indices.

As an example, say you pick row/column indices $i$ and $j$. Then you include matrix where you first replace $i$th row with transpose of $i$th column and vice versa followed by similar operation on $j$th row and column.

What is worst case difference between least rank and largest rank of any matrix in $\mathscr{M}[m^\sigma]$?

Can we say anything about their ratios (such as bound based on some intrinsic property of the matrix)?

I am guessing there is a constant $c\in[1,4]$ such that ratio of largest rank to least rank is bounded above by $c$. My guess is $c=4$.

  • $\begingroup$ What does it mean to swap rows for columns? In particular, what is the result of swapping the first row for the second column in $\pmatrix{a&b\cr c&d\cr}$ ? $\endgroup$ Jul 5, 2015 at 4:16
  • $\begingroup$ Corrected swapping. $\endgroup$
    – Turbo
    Jul 5, 2015 at 4:39
  • $\begingroup$ I am downvoting because you are not explaining yourself at all. Add an example! $\endgroup$ Jul 5, 2015 at 12:10
  • $\begingroup$ Your example adds to my confusion. If $S_i$ is the operation that "swaps" the $i$th row and column, and if I understand what "swap" means, then it seems that the $S_i$ commute with each other. But your example suggests that the results of applying $S_iS_j$ and $S_jS_i$ are different. So I'm back to believing that I don't know what "swap" means. $\endgroup$ Jul 5, 2015 at 13:16
  • 1
    $\begingroup$ Ah. I see that you've changed your example to respond to my last comment, but without bothering to mention or acknowledge it. $\endgroup$ Jul 5, 2015 at 15:20

2 Answers 2


Sorry for the multiple deletions and edits; I hope this partial answer will serve as partial penance.

Up to switching some rows and columns, your operation is $$\pmatrix{A&B\cr C&D\cr}\mapsto \pmatrix{A^T&C^T\cr B^T&D\cr}$$ where $A$ and $D$ are square.

Edited to add: Since you still haven't clarified what "swapping" means, it's possible that $A^T$ should be $A$ above. Fortunately, the argument to follow works either way.

I claim that if $A$ is invertible, then the worst-case ratio is $3$. To see this, put $X=CA^{-1}B$, and note that the ranks of the original and transformed matrices are $$rk(A)+rk(D-X)\qquad\hbox{and}\qquad rk(A)+rk(D-X^T)$$

Note that $rk(D-X)$ and $rk(D-X^T)$ are both bounded below by $|rk(D)-rk(A)|$ and above by $rk(D)+rk(A)$. Treating the cases $rk(D)\le rk(A)$ and $rk(D)\ge rk(A)$ separately, it follows in either case that $${rk(A)+rk(D-X)\over rk(A)+rk(D-X^T)}\le 3$$

This settles the case where $A$ is invertible, and does not use the assumption that all entries are $\pm 1$. Of course at the opposite extreme, when $A=0$, your ratio is equal to $1$.

  • $\begingroup$ I also think it is $4$. $\endgroup$
    – Turbo
    Jul 9, 2015 at 5:43
  • $\begingroup$ In your comment to my answer, your operation did not transpose $A$ and I thought you were right at the time. Is this a typo? $\endgroup$ Jul 23, 2015 at 16:35
  • $\begingroup$ @BrendanMcKay: Actually, I'm back to not being sure what "swapping" means, so the operation might be as in my comment or as above. Fortunately, the above argument works either way. I've included an edit to mention this. $\endgroup$ Jul 23, 2015 at 20:57

Take a matrix of order $n$, with $n$ even, so that every entry is $+1$ except for the upper right quarter, which is a nonsingular matrix of order $n/2$. The rank is either $n/2$ or $n/2+1$. Now replace the first $n/2$ rows by the first $n/2$ columns. The new matrix has rank $1$. However, if the last $n/2$ rows are replaced by the first $n/2$ columns, the rank remains the same. So there is no uniform bound on the ratio you seek.

On the other hand, if the original matrix has full rank $n$, the new matrix has rank at least $n/2$, so it may be possible to save something by tightening the conditions. Either put a lower bound on the original rank or an upper bound on the number of rows replaced.

  • $\begingroup$ I am not replacing. I am swapping. Pick a row and a column, swap their roles. $\endgroup$
    – Turbo
    Jul 5, 2015 at 4:26
  • $\begingroup$ Then I don't understand the question. How do you swap the roles of a row and column? $\endgroup$ Jul 5, 2015 at 10:31
  • $\begingroup$ If say if you swap row 1 by column 1, then row 1=transpose of column 1 and column 1=transpose of row 1. $\endgroup$
    – Turbo
    Jul 5, 2015 at 12:57
  • $\begingroup$ @BrendanMcKay: The operation seems to be $$\pmatrix{A&B\cr C&D\cr}\mapsto \pmatrix {A&C^T\cr B^T&D\cr}$$ where $A$ and $D$ are square matrices (perhaps of different sizes), $C$ and $D$ are rectangular of appropriate sizes, and the upper-$T$ denotes the transpose. $\endgroup$ Jul 9, 2015 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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