I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' quantity.

Ideally, this should help me, given knowledge of such a topological feature, to give an upper bound on $d$.

How does the situation change if considering a weighted graph, such as the transition relation of a Markov chain?

Context: I have a nonnegative matrix $Q$ (representing the transition relation of a generic Markov chain restricted to transient states) and a column vector $v$ (representing a generic initial sub-distribution on states). It is known that the least integer $m$ such that for each vector $v$ the Krylov space $K_m(A,v)=\mathrm{span}\{v, Qv, Q^2 v,...,Q^{m-1}v\}$ is $Q$-invariant, is $m=d$, where $d$ is the degree of the minimal polynomial of $Q$. I'm trying to understand the relationship between this $d$ and the 'topology' of $Q$ seen as a graph, in the above sense. Assume there is only one connected component in the graph of $Q$.

Any reference to this problem would be greatly appreciated.

Best, Michele

  • $\begingroup$ Is the matrix $Q$ symmetric, and assuming that it's not, can it be reformulated to be symmetric? Spectral theory for undirected graphs are significantly more mature than those for directed graphs, which are inherently harder to analyze. $\endgroup$ – Richard Zhang Nov 4 '14 at 22:42
  • 2
    $\begingroup$ Your statement on Krylov subspaces seems false; counterexample: take $v$ equal to an eigenvector of $Q$. The claim holds if you reverse the order of quantifiers (the least $m$ such that for each $v$ $K_m(A,v)$ is $Q$-invariant is $d$). $\endgroup$ – Federico Poloni Nov 4 '14 at 22:57

Let $G$ denote the graph associated with $Q$. Note that $G$ is strongly connected under your assumptions. The following results hold in general: $$D \le d \le n,$$ where $D$ and $n$ are the diameter and size of $G$, respectively.

The upper bound follows from Cayley-Hamilton theorem. The lower bound can be shown by contradiction; in particular, assume $D \ge d+1$, then there exists a (directed) path $i\to j$ of length $D$. Then consider vector $v = [0,\ldots, 1_i,0,\ldots,0]^T \in \mathbb{R}^n$. Then $K_d(Q,v) = \{0\}$ while $Q^Dv \neq 0$. You can easily find graphs such that the bounds above are achievable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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