6
$\begingroup$

Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries $$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\ -1 &\text{if $e$ points from $v$}\\ 0 &\text{otherwise.} \end{cases} $$ If $(V,E)$ is a tree, then this matrix has one more row than being square.

If we erase the row corresponding to a vertex $v$, the resulting square matrix is easily seen to have determinant $\pm 1$ or $0$. Is there a simple, known formula for its determinant? (Surely!)

Example: consider $1 \stackrel{1}{\to} 2 \stackrel{2}{\to} 3$, with matrix $ \begin{pmatrix} -1&0\\ 1&-1\\ 0&1 \end{pmatrix}$. Then the three choices $v=1,2,3$ give the determinants $1,-1,1$ respectively.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Expanding darij grinberg's comment --- it looks like the answer is $(-1)^n$ where $n$ is the number of "$v$-antioriented edges", i.e. the number of edges orientation of which should be switched to make all edges oriented from $v$. $\endgroup$
    – Sasha
    Commented Nov 23, 2014 at 10:08

2 Answers 2

Reset to default
2
$\begingroup$

I may be missing something. The determinant is zero if $v$ is a cut vertex, equivalently not a vertex of degree one, and is otherwise $\pm1$. (This all follows from standard properties of oriented incidence matrices of graphs.) The sign of the determinant with depend on the chosen ordering of vertices and edges.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I want to know whether it's $1$ or $-1$. $\endgroup$
    – Allen Knutson
    Commented Nov 23, 2014 at 2:46
  • 1
    $\begingroup$ @ChrisGodsil: I don't think it will be $0$. $\endgroup$
    – darij grinberg
    Commented Nov 23, 2014 at 3:33
  • 1
    $\begingroup$ @AllenKnutson: I'm not sure how explicit you want it. Algorithmically, it is simple: Re-orient all edges away from the vertex $v$, thus making $v$ the root of the tree. Remove $v$, thus obtaining a forest and some dangling edges with only a target but no source. Label the vertices increasingly (i.e., for every edge $a \to b$, we must have $a < b$). Label the edges such that the label of every edge is that of its target (this is possibly because every vertex is now the target of exactly one edge). Then, the determinant is $1$ since the matrix is unitriangular. $\endgroup$
    – darij grinberg
    Commented Nov 23, 2014 at 3:34
  • $\begingroup$ I added an example to show a cut vertex in action; darij is right. $\endgroup$
    – Allen Knutson
    Commented Nov 23, 2014 at 3:48
  • $\begingroup$ Forget the sentence where I said to label the vertices increasingly. This is not necessary. Whatever way they are labelled, as long as the edges are labelled accordingly, the matrix will still be unitriangular for an appropriate choice of labels for both rows and columns (and the choice for rows is the same as the choice for columns, so different choices do not force different signs), and so the determinant will still be $1$. $\endgroup$
    – darij grinberg
    Commented Nov 23, 2014 at 4:28
2
$\begingroup$

A matrix is said to be totally unimodular if the determinant of any square submatrix of the matrix is either $0$ or $\pm 1.$ Let $G$ be a graph with incidence matrix $Q(G)$, that is, a matrix corresponding to a finite oriented directed graph of $G$. It is easily proved by induction on the order of the submatrix that $Q(G)$ is totally unimodular. The proof is taken from the book (Lemma 2.6) Bapat RB. Graphs and matrices. New York: Springer; 2010 Jul 23.

Proof: Consider the statement that any $k\times k$ submatrix of $Q(G)$ has determinant $0$ or $\pm1.$ We prove the statement by induction on $k$. Clearly the statement holds for $k=1,$ since each entry of $Q(G)$ is either $0$ or $\pm1.$ Assume the statement to be true for $k-1$ and consider a $k\times k$ submatrix $B$ of $Q(G)$. If each column of $B$ has a 1 and a $-1$, then $\det B=0.$ Also, if $B$ has a zero column, the $\det B=0.$ Now suppose $B$ has a coumn with only one nonzero entry, which must be $\pm1.$ Expand the determinant of $B$ along that column and use induction assumption to conclude that $\det B$ must be 0 or $\pm1.$

If $G$ is tree on $n$ vertices, then any submatrix of $Q(G)$ of order $n-1$ is nonsingular.

Proof: Consider the submatrix $X$ of $Q(G)$ formed by the rows $1,\dots, n-1.$ If we add all the rows of $X$ to the last row, then the last row of $X$ becomes the negative of the last row of $Q(G)$. Thus, if $Y$ denotes the submatrix of $Q(G)$ formed by the rows $1,\dots,n-2,n,$ then $\det X=-\det Y.$ Thu, if $\det X=0,$ then $\det Y=0.$ Continuing this way we can show that if $\det X=0$ then each $(n-1)\times (n-1)$ submatrix of $Q(G)$ must be singular. In fact, we can show that if any one of the $(n-1)\times (n-1)$ submatrices of $Q(G)$ is singular, then all them must be so. However, rank $Q(G)=n-1$ and hence at least one of the $(n-1)\times (n-1)$ submatrices of $Q(G)$ must be nonsingular.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .