# A property of incidence matrix of a graph

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 ?

-
The answer seems to be almost trivially yes -- clearly $B$ may contain a zero, and if it does, then the two permutations just have to map one index such that this zero is included in the products, and can differ arbitrarily on all other indices. Am I missing something? –  joriki Feb 13 '13 at 7:10
@joriki: Exteremely sorry, I made a typo; I wanted to ask whether the products are non-zero, fixed. –  pritam Feb 14 '13 at 11:35

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

-

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.

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$$- I think the$b$s should be$q$s, or the indices should go from$1$to$3$. – joriki Feb 14 '13 at 11:45 I think you are assuming$G$is undirected but I mentioned$G$is a directed graph, then each coloumn (which corresponds to edges) must have exactly one$1$, one$-1\$ and rest zero –  pritam Feb 14 '13 at 11:58