# What is the criterion for a matrix containing vectors and their permutations being invertible?

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$.

Example

$$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$).

Conjectures

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.

• 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.) – Mark Wildon Oct 23 '15 at 13:32
• @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. – Rob Oct 23 '15 at 14:52
• 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. – Nick Gill Oct 23 '15 at 15:07
• 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). – Nick Gill Oct 23 '15 at 15:07
• 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$. – Rob Oct 23 '15 at 15:27

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...
• So, am I right that what you really need is $\det B\neq 0$ as a polynomial in elements of $A$? – Ilya Bogdanov Oct 25 '15 at 11:06