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.

derangementis 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 thatmatrix $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:07supportof a permutation (this being the complement to the set of fixed points). $\endgroup$ – Nick Gill Oct 23 '15 at 15:07matrix $B$ is invertible if $P$ has at most one fixed point. For $m=2$ it is indeed anif and only ifrelation, 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:272more comments