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$ – Steven Landsburg Jul 5 '15 at 4:16
  • $\begingroup$ Corrected swapping. $\endgroup$ – 1.. Jul 5 '15 at 4:39
  • $\begingroup$ I am downvoting because you are not explaining yourself at all. Add an example! $\endgroup$ – Federico Poloni Jul 5 '15 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$ – Steven Landsburg Jul 5 '15 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$ – Steven Landsburg Jul 5 '15 at 15:20

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$ – 1.. Jul 9 '15 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$ – Brendan McKay Jul 23 '15 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$ – Steven Landsburg Jul 23 '15 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$ – 1.. Jul 5 '15 at 4:26
  • $\begingroup$ Then I don't understand the question. How do you swap the roles of a row and column? $\endgroup$ – Brendan McKay Jul 5 '15 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$ – 1.. Jul 5 '15 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$ – Steven Landsburg Jul 9 '15 at 6:05

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.