Consider the matrix $A\in\mathbb{R}^{m\times 2m}$. Let any arbitrary choice of $m$ columns of $A$ be linearly independent. Together with a permutation $P\in\mathcal{P_{2m}}$, one can build the matrix $$B:=\begin{bmatrix}A\\AP\end{bmatrix}\in\mathbb{R}^{2m\times 2m}\text{ .}$$ Which conditions does $P$ need to satisfy, so that $B$ is invertible? I would like to have just a criterion for the matrix P.

The rest of this post shows an example and conjectures I already have from experiments. I had a look at $4\times 4$, $6\times 6$, $8\times 8$ and $10\times 10$ matrices $A$, all permutations $P$ and the determinants of $B$.


$$B_1=\begin{bmatrix} a_1&b_1&c_1&d_1\\ a_2&b_2&c_2&d_2\\\hline \mathbf{b_1}&\mathbf{a_1}&c_1&d_1\\ \mathbf{b_2}&\mathbf{a_2}&c_2&d_2\\ \end{bmatrix}\qquad ,\qquad B_2=\begin{bmatrix} a_1&b_1&c_1&d_1\\ a_2&b_2&c_2&d_2\\\hline \mathbf{c_1}&\mathbf{a_1}&\mathbf{b_1}&d_1\\ \mathbf{c_2}&\mathbf{a_2}&\mathbf{b_2}&d_2\\ \end{bmatrix}$$ $B_1$ is always singular ($\det B_1=0$) and $B_2$ always invertible ($\det B_2\neq 0$).


What helps is looking at derangements. A derangement is a permutation which does not assign an element its original position. It is said that the elements are deranged.

Conjecture 1: Matrix $B$ is invertible if at least $2m-1$ columns of $A$ are deranged by $P$.

Conjecture 2: The matrix $B$ is regular if at least $m+1$ columns of $A$ are deranged by $P$ and the permutation consists of a cycle of at least size $m$.

Both conjectures are no "if and only if" relations. There are definitely permutations which do not fulfill the criterion but lead to invertible $B$'s. What I also saw when I was investigating small $m$'s was, that all permutations with the same number and sizes of cycles always lead to the same result. In the example $B_1$ has one cycle of size 2 and every permutation with a single cycle and size 2 leads to a singular matrix. $B_2$'s permutation has one cycle of size 3 and every such permutation lead to an invertible matrix $B_2$.

I would be happy if I could show at least conjecture 1 for all $m$. Conjecture 2 would be even better. But I don't have an idea how. Any other criterion of $P$ leading to an invertible matrix $B$ are fine as well.

  • $\begingroup$ Surely the second sentence should say 'linearly dependent', not 'linearly independent'? And do you want any $m$ columns to be linearly dependent, or just some $m$ columns to be linearly dependent? (I'm guessing the former.) $\endgroup$ – Mark Wildon Oct 23 '15 at 13:32
  • $\begingroup$ @MarkWildon Why do you think so? No, I mean linearly independent. Or in other words every $m \times m$ submatrix of A, consisting of $m$ different columns of $A$, should be invertible. $\endgroup$ – Rob Oct 23 '15 at 14:52
  • 1
    $\begingroup$ I'm not sure if I've understood you correctly, but I think your use of the verb "deranged" is inadvisable. A derangement is used in the very special setting where a permutation has no fixed points at all, whereas your first conjecture concerns permutations that have at most one fixed point. If I understand your first conjecture correctly, you're really asserting that matrix $B$ is invertible if and only if the permutation associated to $P$ has at most one fixed point. A similar rewording would apply for Conjecture 2. $\endgroup$ – Nick Gill Oct 23 '15 at 15:07
  • 1
    $\begingroup$ While we're doing about terminology, you might also want to look into results on the support of a permutation (this being the complement to the set of fixed points). $\endgroup$ – Nick Gill Oct 23 '15 at 15:07
  • $\begingroup$ Yes, you are right, it's a bit confusing. I mean permutations with at most one fixed point in the first conjecture. And no, I am just asserting matrix $B$ is invertible if $P$ has at most one fixed point. For $m=2$ it is indeed an if and only if relation, but for greater $m$ there are cases, in which a permutation with up to $m-1$ fixed points lead to an invertible matrix $B$. $\endgroup$ – Rob Oct 23 '15 at 15:27

Sorry, these are perhaps two remarks, but they are a bit large for a comment.

Generally, you may multiply $B$ by $\begin{bmatrix}X^{-1}&0\\0&X^{-1}\end{bmatrix}$ where $X$ is the left half of $A$, thus assuming that $A=\begin{bmatrix}E&Y\end{bmatrix}$. In this case, the formula $$ \det\begin{bmatrix}E&Y\\Z&T\end{bmatrix} =\det\begin{bmatrix}E&Y\\0&T-ZY\end{bmatrix} =\det(T-ZY) $$ may be helpful.

Specifically, I do not see that $B_2$ is always invertible. Putting $Y=\begin{bmatrix}-1&1\\-1&2\end{bmatrix}$ (all pairs of columns of $A$ are independent!), then you get $$ \det B_2=\det\begin{bmatrix}1&0&-1&1\\0&1&-1&2\\-1&1&0&1\\-1&0&1&2\end{bmatrix}=0 $$ (the formula above may help). This seems to disprove both conjectures...

  • $\begingroup$ Thanks! Yes, I am using this representation already.The example is very interesting! I just tried with random numbers. I couldn't believe that it is not dependent on the numbers themselves either, but could think of an example. For random numbers with the mentioned condition the conjectures seem to be true. $\endgroup$ – Rob Oct 24 '15 at 15:26
  • $\begingroup$ So, am I right that what you really need is $\det B\neq 0$ as a polynomial in elements of $A$? $\endgroup$ – Ilya Bogdanov Oct 25 '15 at 11:06
  • $\begingroup$ Hmm, yes, I guess so. $\endgroup$ – Rob Oct 26 '15 at 7:03

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.