A property of incidence matrix of a graph

Question

Let $G$ be an oriented graph with incidence matrix $Q$, and let $B:=[b_{ij}]$ be a $k\times k$ sub-matrix of $Q$ which is non-singular. Can there exist two distinct permutations $\sigma$ and $\sigma^\prime$ of $1,\ldots ,k$ for which both the products $b_{1\sigma (1)}\cdots b_{k\sigma (k)}$ and $ b_{1\sigma^\prime (1)}\cdots b_{k\sigma^\prime (k)}$ are non-zero ?

Answer 1

If a set of columns of the incidence matrix of an oriented graph is linearly independent, then the corresponding edges form a forest. Suppose we choose $k$ columns, and then choose $k$ rows from these to form a non-singular matrix $M$.

Claim: there is a column of $M$ with exactly one non-zero entry in it. For otherwise each column contains a $1$ and a $-1$ and so the sum of the rows of $M$ is zero. Since $M$ is invertible, this is impossible.

Note that any two permutations with nonzero products must both use this entry of $M$

Note also that if we delete from $M$ a column with exactly one nonzero entry, and also delete the row that contained it, the resulting $(k-1)\times(k-1)$ matrix is still non-singular. The result follows by induction on $k$.

Answer 2

MORE EDIT: The edit was wrong, the matrix I wrote down is singular. Nothing worth looking at here.

EDIT: let $Q$ have a submatrix $$\pmatrix{1&0&0&-1\cr-1&1&0&0\cr0&-1&1&0\cr0&0&-1&1\cr}$$ The submatrix is nonsingular, and you can find a permutation that gets all the $1$s, and a different permutation that gets all the $-1$s, and the products will be equal and nonzero.

Please ignore what follows.

Maybe I don't understand the problem, but if $$Q=\pmatrix{0&1&1&0&1\cr0&0&1&1&0\cr0&0&0&1&1\cr0&0&0&0&1\cr0&0&0&0&0\cr}$$ then $$\pmatrix{1&0&1\cr1&1&0\cr0&1&1\cr}$$ is a non-singular $3\times3$ submatrix, and $b_{13}b_{24}b_{35}=b_{15}b_{23}b_{34}=1\ne0$$