The Azimuth Project
Blog - network theory (part 20)

This page is a blog article in progress, written by Jacob Biamonte. To see discussions of this article as it is being written, go the Azimuth Forum. For the final polished version, visit the Azimuth Blog.

guest post by Jacob Biamonte

We’re in the middle of a battle: in addition to our typical man vs. equation scenario, it’s a battle between two theories. For those good patrons following the network theory series, you know the two opposing forces well. It’s our old friends, at it again:

Stochastic Mechanics vs Quantum Mechanics!

Today we’re reporting live from a crossroads, and we’re facing a skirmish that gives rise to what some might consider a paradox. Let me sketch the main thesis before we get our hands dirty with the gory details.

First I need to tell you that the battle takes place at the intersection of stochastic and quantum mechanics. We recall from Part 16 that there is a class of operators called ‘Dirichlet operators’ that are valid Hamiltonians for both stochastic and quantum mechanics. In other words, you can use them to generate time evolution both for old-fashioned random processes and for quantum processes!

Staying inside this class allows the theories to fight it out on the same turf. We will be considering a special subclass of Dirichlet operators, which we call ‘irreducible Dirichlet operators’. These are the ones where starting in any state in our favorite basis of states, we have a nonzero chance of winding up in any other. When considering this subclass, we found something interesting:

Thesis. Let HH be an irreducible Dirichlet operator with nn eigenstates. In stochastic mechanics, there is only one valid state that is an eigenvector of HH: the unique so-called ‘Perron–Frobenius state’. The other n1n-1 eigenvectors are forbidden states of a stochastic system: the stochastic system is either in the Perron–Frobenius state, or in a superposition of at least two eigensvectors. In quantum mechanics, all nn eigenstates of HH are valid states.

This might sound like a riddle, but today as we’ll prove, riddle or not, it’s a fact. If it makes sense, well that’s another issue. As John might have said, it’s like a bone kicked down from the gods up above: we can either choose to chew on it, or let it be. Today we are going to do a bit of chewing.

One of the many problems with this post is that John had a nut loose on his keyboard. It was not broken! I’m saying he wrote enough blog posts on this stuff to turn them into a book. I’m supposed to be compiling the blog articles into a massive LaTeX file, but I wrote this instead.

Another problem is that this post somehow seems to use just about everything said before, so I’m going to have to do my best to make things self-contained. Please bear with me as I try to recap what’s been done. For those of you familiar with the series, a good portion of the background for what we’ll cover today can be found in Part 12 and Part 16.

At the intersection of two theories

As John has mentioned in his recent talks, the typical view of how quantum mechanics and probability theory come into contact looks like this:

The idea is that quantum theory generalizes classical probability theory by considering observables that don’t commute.

That’s perfectly valid, but we’ve been exploring an alternative view in this series. Here quantum theory doesn’t subsume probability theory, but they intersect:

What goes in the middle you might ask? As odd as it might sound at first, John showed in Part 16 that electrical circuits made of resistors constitute the intersection!

For example, a circuit like this:

gives rise to a Hamiltonian HH that’s good both for stochastic mechanics and stochastic mechanics. Indeed, he found that the power dissipated by a circuit made of resistors is related to the familiar quantum theory concept known as the expectation value of the Hamiltonian!

power=2ψ,Hψ power = -2 \langle \psi, H \psi \rangle

Oh—and you might think we’ve made a mistake and wrote our Ω (ohm) symbols upside down. We didn’t. It happens that ℧ is the symbol for a ‘mho’—a unit of conductance that’s the reciprocal of an ohm. Check out Part 16 for the details.

Stochastic mechanics versus quantum mechanics

Let’s recall how states, time evolution, symmetries and observables work in the two theories. Today we’ll fix a basis for our vector space of states, and we’ll assume it’s finite-dimensional so that all vectors have nn components over either the complex numbers \mathbb{C} or the reals \mathbb{R}. In other words, we’ll treat our space as either n \mathbb{C}^n or n \mathbb{R}^n. In this fashion, linear operators that map such spaces to themselves will be represented as square matrices.

Vectors will be written as ψ i\psi_i where the index ii runs from 1 to nn, and we think of each choice of the index as a state of our system—but since we’ll be using that word in other ways too, let’s call it a configuration. It’s just a basic way our system can be.

States

Besides the configurations i=1,,ni = 1,\dots, n, we have more general states that tell us the probability or amplitude of finding our system in one of these configurations:

Stochastic states are nn-tuples of nonnegative real numbers:

ψ i + \psi_i \in \mathbb{R}^+

The probability of finding the system in the iith configuration is defined to be ψ i\psi_i. For these probabilities to sum to one, ψ i\psi_i needs to be normalized like this:

iψ i=1 \sum_i \psi_i = 1

or in the notation we’re using in these articles:

ψ=1 \langle \psi \rangle = 1

where we define

ψ= iψ i \langle \psi \rangle = \sum_i \psi_i

Quantum states are nn-tuples of complex numbers:

ψ i \psi_i \in \mathbb{C}

The probability of finding a state in the iith configuration is defined to be |ψ(x)| 2|\psi(x)|^2. For these probabilities to sum to one, ψ\psi needs to be normalized like this:

i|ψ i| 2=1 \sum_i |\psi_i|^2 = 1

or in other words

ψ,ψ=1 \langle \psi, \psi \rangle = 1

where the inner product of two vectors ψ\psi and ϕ\phi is defined by

ψ,ϕ= iψ¯ iϕ i \langle \psi, \phi \rangle = \sum_i \overline{\psi}_i \phi_i

Now, the usual way to turn a quantum state ψ\psi into a stochastic state is to take the absolute value of each number ψ i\psi_i and then square it. However, if the numbers ψ i\psi_i happen to be nonnegative, we can also turn ψ\psi into a stochastic state simply by multiplying it by a number to ensure ψ=1\langle \psi \rangle = 1.

This is very unorthodox, but it lets us evolve the same vector ψ\psi either stochastically or quantum-mechanically, using the recipes I’ll describe next. In physics jargon these correspond to evolution in ‘real time’ and ‘imaginary time’. But don’t ask me which is which: from a quantum viewpoint stochastic mechanics uses imaginary time, but from a stochastic viewpoint it’s the other way around!

Time evolution

Time evolution works similarly in stochastic and quantum mechanics, but with a few big differences:

• In stochastic mechanics the state changes in time according to the master equation:

ddtψ(t)=Hψ(t) \frac{d}{d t} \psi(t) = H \psi(t)

which has the solution

ψ(t)=exp(tH)ψ(0) \psi(t) = \exp(t H) \psi(0)

• In quantum mechanics the state changes in time according to Schrödinger’s equation:

ddtψ(t)=iHψ(t) \frac{d}{d t} \psi(t) = -i H \psi(t)

which has the solution

ψ(t)=exp(itH)ψ(0) \psi(t) = \exp(-i t H) \psi(0)

The operator HH is called the Hamiltonian. The properties it must have depend on whether we’re doing stochastic mechanics or quantum mechanics:

• We need HH to be infinitesimal stochastic for time evolution given by exp(itH)\exp(-i t H) to send stochastic states to stochastic states. In other words, we need that (i) its columns sum to zero and (ii) its off-diagonal entries are real and nonnegative:

iH ij=0 \sum_i H_{i j}=0
ijH ij0 i\neq j\Rightarrow H_{i j}\geq 0

• We need H H to be self-adjoint for time evolution given by exp(tH)\exp(-t H) to send quantum states to quantum states. So, we need

H=H H = H^\dagger

where we recall that the adjoint of a matrix is the conjugate of its transpose:

(H ) ij:=H¯ ji (H^\dagger)_{i j} := \overline{H}_{j i}

We are concerned with the case where the operator H H generates both a valid quantum evolution and also a valid stochastic one:

HH is a Dirichlet operator if it’s both self-adjoint and infinitesimal stochastic.

We will soon go further and zoom in on this intersection! But first let’s finish our review.

Symmetries

As John explained in Part 12, besides states and observables we need symmetries, which are transformations that map states to states. These include the evolution operators which we only briefly discussed in the preceding subsection.

• A linear map UU that sends quantum states to quantum states is called an isometry, and isometries are characterized by this property:

U U=1 U^\dagger U = 1

• A linear map UU that sends stochastic states to stochastic states is called a stochastic operator, and stochastic operators are characterized by these properties:

iU ij=1 \sum_i U_{i j} = 1

and

U ij0 U_{i j}\geq 0

A notable difference here is that in our finite-dimensional situation, isometries are always invertible, but stochastic operators may not be! If UU is an n×nn \times n matrix that’s an isometry, U U^\dagger is its inverse. So, we also have

UU =1 U U^\dagger = 1

and we say UU is unitary. But if UU is stochastic, it may not have an inverse—and even if it does, its inverse is rarely stochastic. This explains why in stochastic mechanics time evolution is often not reversible, while in quantum mechanics it always is.

Puzzle 1. Suppose UU is a stochastic n×nn \times n matrix whose inverse is stochastic. What are the possibilities for UU?

It is quite hard for an operator to be a symmetry in both stochastic and quantum mechanics, especially in our finite-dimensional situation:

Puzzle 2. Suppose UU is an n×nn \times n matrix that is both stochastic and unitary. What are the possibilities for UU?

Observables

‘Observables’ are real-valued quantities that can be measured, or predicted, given a specific theory.

• In quantum mechanics, an observable is given by a self-adjoint matrix OO, and the expected value of the observable OO in the quantum state ψ\psi is

ψ,Oψ= i,jψ¯ iO ijψ j \langle \psi , O \psi \rangle = \sum_{i,j} \overline{\psi}_i O_{i j} \psi_j

• In stochastic mechanics, observables assign a real number A iA_i to each configuration ii, and the expected value of the observable AA in the stochastic state ψ\psi is

Oψ= iO iψ i \langle O \psi \rangle = \sum_i O_i \psi_i

We can turn an observable in stochastic mechanics into an observable in quantum mechanics by making a diagonal matrix whose diagonal entries are the numbers O iO_i.

From graphs to matrices

Back in Part 16, John explained how a graph with positive numbers on its edges gives rise to a Hamiltonian in both quantum and stochastic mechanics—in other words, a Dirichlet operator.

Here’s how this works. We’ll consider simple graphs: graphs without arrows on their edges, with at most one edge from one vertex to another, with no edges from a vertex to itself. And we’ll only look at graphs with finitely many vertices and edges. We’ll assume each edge is labelled by a positive number, like this:

If our graph has nn vertices, we can create an n×nn \times n matrix AA where A ijA_{i j} is the number labelling the edge from ii to jj, if there is such an edge, and 0 if there’s not. This matrix is symmetric, with real entries, so it’s self-adjoint. So AA is a valid Hamiltonian in quantum mechanics.

How about stochastic mechanics? Remember that a Hamiltonian in stochastic mechanics needs to be ‘infinitesimal stochastic’. So, its off-diagonal entries must be nonnegative, which is indeed true for our AA, but also the sums of its columns must be zero, which is not true when our AA is nonzero.

But now comes the best news you’ve heard all day: we can improve AA to a stochastic operator in a way that is completely determined by AA itself! This is done by subtracting a diagonal matrix LL whose entries are the sums of the columns of AA:

L ii= iA ijL_{i i} = \sum_i A_{i j}
ijL ij=0 i \ne j \Rightarrow L_{i j} = 0

It’s easy to check that

H=AL H = A - L

is still self-adjoint, but now also infinitesimal stochastic. So, it’s a Dirichlet operator: a good Hamiltonian for both stochastic and quantum mechanics!

In Part 16, we saw a bit more: every Dirichlet operator arises this way. It’s easy to see. You just take your Dirichlet operator and make a graph with one edge for each nonzero off-diagonal entry. Then you label the edge with this entry. So, Dirichlet operators are essentially the same as finite simple graphs with edges labelled by positive numbers.

Now, a simple graph can consist of many separate ‘pieces’, called components. Then there’s no way for a particle hopping along the edges to get from one component to another, either in stochastic or quantum mechanics. So we might as well focus our attention on graphs with just one component. These graphs are called ‘connected’. In other words:

Definition. A simple graph is connected if it is nonempty and there is a path of edges connecting any vertex to any other.

Our goal today is to understand more about Dirichlet operators coming from connected graphs. For this we need to learn the Perron–Frobenius theorem. But let’s start with something easier.

Perron's theorem

In quantum mechanics it’s good to think about observables that have positive expected values:

ψ,Oψ>0 \langle \psi, O \psi \rangle > 0

for every quantum state ψ n\psi \in \mathbb{C}^n. These are called positive definite. But in stochastic mechanics it’s good to think about matrices that are positive in a more naive sense:

Definition. An n×nn \times n real matrix TT is positive if all its entries are positive:

T ij>0 T_{i j} > 0

for all 1i,jn1 \le i, j \le n.

Similarly:

Definition. A vector ψ n\psi \in \mathbb{R}^n is positive if all its components are positive:

ψ i>0 \psi_i > 0

for all 1in1 \le i \le n.

We’ll also define nonnegative matrices and vectors in the same way, replacing >0> 0 by 0\ge 0. A good example of a nonnegative vector is a stochastic state.

In 1907, Perron proved the following fundamental result about positive matrices:

Perron’s Theorem. Given a positive square matrix TT, there is a positive real number rr, called the Perron-–Frobenius eigenvalue of TT, such that rr is an eigenvalue of TT and any other eigenvalue λ\lambda of TT has |λ|<r |\lambda| &lt; r. Moreover, there is a positive vector ψ n\psi \in \mathbb{R}^n with Tψ=rψT \psi = r \psi. Any other vector with this property is a scalar multiple of ψ\psi. Furthermore, any nonnegative vector that is an eigenvector of TT must be a scalar multiple of ψ\psi.

In other words, if TT is positive, it has a unique eigenvalue with the largest absolute value. This eigenvalue is positive. Up to a constant factor, it has an unique eigenvector. We can choose this eigenvector to be positive. And then, up to a constant factor, it’s the only nonnegative eigenvector of TT.

From matrices to graphs

The conclusions of Perron’s theorem don’t hold for matrices that are merely nonnegative. For example, these matrices

(1 0 0 1),(0 1 0 0) \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) , \qquad \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array} \right)

are nonnegative, but they violate lots of the conclusions of Perron’s theorem.

Nonetheless, in 1912 Frobenius published an impressive generalization of Perron’s result. In its strongest form, it doesn’t apply to all nonnegative matrices; only to those that are ‘irreducible’. So, let us define those.

We’ve seen how to build a matrix from a graph. Now we need to build a graph from a matrix! Suppose we have an n×nn \times n matrix TT. Then we can build a graph G TG_T with nn vertices where there is an edge from the iith vertex to the jjth vertex if and only if T ij0T_{i j} \ne 0.

But watch out: this is a different kind of graph! It’s a directed graph, meaning the edges have directions, there’s at most one edge going from one vertex to another, and we do allow an edge going from a vertex to itself. There’s a stronger concept of ‘connectivity’ for these graphs:

Definition. A directed graph is strongly connected if there is a directed path of edges going from any vertex to any other vertex.

So, you have to be able to walk along edges from any vertex to any other vertex, but always following the direction of the edges! Using this idea we define irreducible matrices:

Definition. A nonnegative square matrix TT is irreducible if its graph G TG_T is strongly connected.

The Perron--Frobenius theorem

Now we are ready to state:

The Perron-Frobenius Theorem. Given an irreducible nonnegative square matrix TT, there is a positive real number rr, called the Perron-–Frobenius eigenvalue of TT, such that rr is an eigenvalue of TT and any other eigenvalue λ\lambda of TT has |λ|r|\lambda| \le r. Moreover, there is a positive vector ψ n\psi \in \mathbb{R}^n with Tψ=rψT\psi = r \psi. Any other vector with this property is a scalar multiple of ψ\psi. Furthermore, any nonnegative vector that is an eigenvector of TT must be a scalar multiple of ψ\psi.

The only conclusion of this theorem that’s weaker than those of Perron’s theorem is that there may be other eigenvalues with |λ|=r|\lambda| = r. For example, this matrix is irreducible and nonnegative:

(0 1 1 0) \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)

Its Perron–Frobenius eigenvalue is 1, but it also has -1 as an eigenvalue. For any irreducible nonnegative square matrix, Perron-Frobenius theory says quite a lot about the other eigenvalues on the circle |λ|=r,|\lambda| = r, but we won’t need that information here.

Perron–Frobenius theory is useful in many ways, from highbrow math to ranking football teams. We’ll need it not just today but also later in this series. There are many books and other sources of information for those that want to take a closer look at this subject. If you’re interested, you can search online or take a look at these:

I have not taken a look myself, but if anyone is interested and can read German, the original work appears here:

  • Oskar Perron, Zur Theorie der Matrizen, Math. Ann. 64 (1907), 248–263.

  • Georg Frobenius, Über Matrizen aus nicht negativen Elementen, S.-B. Preuss Acad. Wiss. Berlin (1912), 456–477.

And, of course, there’s this:

It’s quite good.

Irreducible Dirichlet operators

Now comes the payoff. We saw how to get a Dirichlet operator HH from any finite simple graph with edges labelled by positive numbers. Now let’s apply Perron–Frobenius theory to prove our thesis.

Unfortunately, the matrix HH is rarely nonnegative. If you remember how we built it, you’ll see its off-diagonal entries will always be nonnegative… but its diagonal entries can be negative.

Luckily, we can fix this just by adding a big enough multiple of the identity matrix to HH! The result is a nonnegative matrix

T=H+cI T = H + c I

where c>0c &gt; 0 is some large number. This matrix TT has the same eigenvectors as HH. The off-diagonal matrix entries of TT are the same as those of AA, so T ijT_{i j} is nonzero for iji \ne j exactly when the graph we started with has an edge from ii to jj. So, for iji \ne j, the graph G TG_T will have an directed edge going from ii to jj precisely when our original graph had an edge from ii to jj. And that means that if our original graph was connected, G TG_T will be strongly connected. Thus, by definition, the matrix TT is irreducible!

Since TT is nonnegative and irreducible, the Perron–Frobenius theorem swings into action and we conclude:

Lemma. Suppose HH is the Dirichlet operator coming from a connected finite simple graph with edges labelled by positive numbers. Then the eigenvalues of HH are real. Let λ\lambda be the largest eigenvalue. Then there is a positive vector ψ n\psi \in \mathbb{R}^n with Hψ=λψH\psi = \lambda \psi. Any other vector with this property is a scalar multiple of ψ\psi. Furthermore, any nonnegative vector that is an eigenvector of HH must be a scalar multiple of ψ\psi.

Proof. The eigenvalues of Harerealsince are real since Hisselfadjoint.Noticethatif is self-adjoint. Notice that if risthePerronFrobeniuseigenvalueof is the Perron--Frobenius eigenvalue of T = H + c I$ and

Tψ=rψ T \psi = r \psi

then

Hψ=(rc)ψ H \psi = (r - c)\psi

By the Perron–Frobenius theorem the number rr is positive, and it has the largest absolute value of any eigenvalue of TT. Thanks to the subtraction, the eigenvalue rcr - c may not have the largest absolute value of any eigenvalue of HH. It is, however, the largest eigenvalue of HH, so we take this as our λ\lambda. The rest follows from the Perron–Frobenius theorem.   █

But in fact we can improve this result, since the largest eigenvalue λ\lambda is just zero. Let’s also make up a definition, to make our result sound more slick:

Definition. A Dirichlet operator is irreducible if it comes from a connected finite simple graph with edges labelled by positive numbers.

This meshes nicely with our earlier definition of irreducibility for nonnegative matrices. Now:

Theorem. Suppose HH is an irreducible Dirichlet operator. Then HH has zero as its largest real eigenvalue. There is a positive vector ψ n\psi \in \mathbb{R}^n with Hψ=0H\psi = 0. Any other vector with this property is a scalar multiple of ψ\psi. Furthermore, any nonnegative vector that is an eigenvector of HH must be a scalar multiple of ψ\psi.

Proof. Choose λ\lambda as in the Lemma, so that Hψ=λψH\psi = \lambda \psi. Since ψ\psi is positive we can normalize it to be a stochastic state:

iψ i=1 \sum_i \psi_i = 1

Since HH is a Dirichlet operator, exp(tH)\exp(t H) sends stochastic states to stochastic states, so

i(exp(tH)ψ) i=1 \sum_i (\exp(t H) \psi)_i = 1

for all t0t \ge 0. On the other hand,

i(exp(tH)ψ) i= ie tλψ i=e tλ \sum_i (\exp(t H)\psi)_i = \sum_i e^{t \lambda} \psi_i = e^{t \lambda}

so we must have λ=0\lambda = 0.   █

What’s the point of all this? One point is that there’s a unique stochastic state ψ\psi that’s an equilibrium state: since Hψ=0H \psi = 0, it doesn’t change with time. It’s also globally stable: since all the other eigenvalues of HH are negative, all other stochastic states converge to this one as time goes forward.

An example

There are many examples of irreducible Dirichlet operators. For instance, in Part 15 we talked about graph Laplacians. The Laplacian of a connected simple graph is always irreducible. But let us try a different sort of example, coming from the picture of the resistors we saw earlier:

Let’s create a matrix AA whose entry A ijA_{i j} is the number labelling the edge from ii to jj if there is such an edge, and zero otherwise:

A=(0 2 1 0 1 2 0 0 1 1 1 0 0 2 1 0 1 2 0 1 1 1 1 1 0)A = \left( \begin{array}{ccccc} 0 & 2 & 1 & 0 & 1 \\ 2 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 2 & 1 \\ 0 & 1 & 2 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{array} \right)

Remember how the game works. The matrix AA is already a valid Hamiltonian for quantum mechanics, since it’s self adjoint. However, to get a valid Hamiltonian for both stochastic and quantum mechanics—in other words, a Dirichlet operator—we subtract the diagonal matrix LL with

L ii= iA ijL_{i i} = \sum_i A_{i j}
ijL ij=0 i \ne j \Rightarrow L_{i j} = 0

In this example it just so happens that L=4IL = 4 I, so our Dirichlet operator is

H=A4I=(4 2 1 0 1 2 4 0 1 1 1 0 4 2 1 0 1 2 4 1 1 1 1 1 4) H = A - 4 I = \left( \begin{array}{ccccc} -4 & 2 & 1 & 0 & 1 \\ 2 & -4 & 0 & 1 & 1 \\ 1 & 0 & -4 & 2 & 1 \\ 0 & 1 & 2 & -4 & 1 \\ 1 & 1 & 1 & 1 & -4 \end{array} \right)

We’ve set up this example so it’s easy to see that the vector ψ=(1,1,1,1,1)\psi = (1,1,1,1,1) has

Hψ=0 H \psi = 0

So, this is the unique eigenvector for the eigenvalue 0. We can use Mathematica to calculate the remaining eigenvalues of HH. The set of eigenvalues is

{0,7,8,8,3}\{0, -7, -8, -8, -3 \}

As we expect from our theorem, the largest real eigenvalue is 0. By design, the eigenstate associated to this eigenvalue is

|v 0=(1,1,1,1,1) | v_0 \rangle = (1, 1, 1, 1, 1)

(This funny notation for vectors is common in quantum mechanics, so don’t worry about it.) All the other eigenvectors fail to be nonnegative, as predicted by the theorem. They are:

|v 1=(1,1,1,1,0), | v_1 \rangle = (1, -1, -1, 1, 0),
|v 2=(1,0,1,0,2), | v_2 \rangle = (-1, 0, -1, 0, 2),
|v 3=(1,1,1,1,0), | v_3 \rangle = (-1, 1, -1, 1, 0),
|v 4=(1,1,1,1,0). | v_4 \rangle = (-1, -1, 1, 1, 0).

To compare the quantum and stochastic states, consider first |v 0 |v_0\rangle. This is the only eigenvector that can be normalized to a stochastic state. Remember, a stochastic state must have nonnegative components. This rules out |v 1 |v_1\rangle through to |v 4 |v_4\rangle as valid stochastic states, no matter how we normalize them! However, these are allowed as states in quantum mechanics, once we normalize them correctly. For a stochastic system to be in a state other than the Perron–Frobenius state, it must be a linear combination of least two eigenstates. For instance,

ψ a=(1a)|v 0+a|v 1 \psi_a = (1-a)|v_0\rangle + a |v_1\rangle

can be normalized to give stochastic state only if 0a12 0 \leq a \leq \frac{1}{2}.

And, it’s easy to see that it works this way for any irreducible Dirichlet operator, thanks to our theorem. So, our thesis has been proved true!

Puzzles on irreducibility

Let us conclude with a couple more puzzles. There are lots of ways to characterize irreducible nonnegative matrices; we don’t need to mention graphs. Here’s one:

Puzzle 3. Let TT be a nonnegative n×nn \times n matrix. Show that TT is irreducible if and only if for all i,j0i,j \ge 0, (T m) ij>0(T^m)_{i j} &gt; 0 for some natural number mm.

You may be confused because today we explained the usual concept of irreducibility for nonnegative matrices, but also defined a concept of irreducibility for Dirichlet operators. Luckily there’s no conflict: Dirichlet operators aren’t nonnegative matrices, but if we add a big multiple of the identity to a Dirichlet operator it becomes a nonnegative matrix, and then:

Puzzle 4. Show that a Dirichlet operator HH is irreducible if and only if the nonnegative operator H+cIH + c I (where cc is any sufficiently large constant) is irreducible.

Irreducibility is also related to the nonexistence of interesting conserved quantities. In Part 11 we saw a version of Noether’s Theorem for stochastic mechanics. Remember that an observable OO in stochastic mechanics assigns a number O iO_i to each configuration i=1,,ni = 1, \dots, n. We can make a diagonal matrix with O iO_i as its diagonal entries, and by abuse of language we call this OO as well. Then we say OO is a conserved quantity for the Hamiltonian HH if the commutator [O,H]=OHHO[O,H] = O H - H O vanishes.

Puzzle 5. Let HH be a Dirichlet operator. Show that HH is irreducible if and only if every conserved quantity OO for HH is a constant, meaning that for some cc \in \mathbb{R} we have O i=cO_i = c for all ii. (Hint: examine the proof of Noether’s theorem.)

In fact this works more generally:

Puzzle 6. Let HH be an infinitesimal stochastic matrix. Show that H+cIH + c I is an irreducible nonnegative matrix for all sufficiently large cc if and only if every conserved quantity OO for HH is a constant.

category: blog