Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
2  
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
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
    
Sorry, you wrote "incidence matrix", but I hallucinated "adjacency matrix". I'll try again. –  Gerry Myerson Feb 14 '13 at 12:09
    
@joriki, you're right. –  Gerry Myerson Feb 14 '13 at 12:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.