*guest post by Jacob Biamonte*

We’re in the middle of a battle: in addition to our typical man versus 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 be an irreducible Dirichlet operator with eigenstates. In stochastic mechanics, there is only one valid state that is an eigenvector of : the unique so-called ‘Perron–Frobenius state’. The other 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 eigenstates of 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 that’s good both for stochastic mechanics and quantum 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!

Oh—and you might think we 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 components over either the complex numbers or the reals In other words, we’ll treat our space as either or In this fashion, linear operators that map such spaces to themselves will be represented as square matrices.

Vectors will be written as where the index runs from 1 to 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 we have more general states that tell us the probability or amplitude of finding our system in one of these configurations:

• **Stochastic states** are -tuples of nonnegative real numbers:

The probability of finding the system in the th configuration is defined to be For these probabilities to sum to one, needs to be normalized like this:

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

where we define

• **Quantum states** are -tuples of complex numbers:

The probability of finding a state in the th configuration is defined to be For these probabilities to sum to one, needs to be normalized like this:

or in other words

where the **inner product** of two vectors and is defined by

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

This is very unorthodox, but it lets us evolve the same vector 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**:

which has the solution

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

which has the solution

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

• We need to be **infinitesimal stochastic** for time evolution given by 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:

• We need to be **self-adjoint** for time evolution given by to send quantum states to quantum states. So, we need

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

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

• 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 that sends quantum states to quantum states is called an **isometry**, and isometries are characterized by this property:

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

and

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

and we say is **unitary**. But if 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 is a stochastic matrix whose inverse is stochastic. What are the possibilities for ?

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 is an matrix that is both stochastic and unitary. What are the possibilities for ?

#### 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 and the expected value of the observable in the quantum state is

• In stochastic mechanics, an observable has a value in each configuration and the expected value of the observable in the stochastic state is

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

### 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 vertices, we can create an matrix where is the number labelling the edge from to 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 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 but also the sums of its columns must be zero, which is not true when our is nonzero.

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

It’s easy to check that

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:

for every quantum state 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 real matrix is **positive** if all its entries are positive:

for all

Similarly:

**Definition.** A vector is **positive** if all its components are positive:

for all

We’ll also define **nonnegative** matrices and vectors in the same way, replacing by 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 there is a positive real number called the **Perron–Frobenius eigenvalue** of such that is an eigenvalue of and any other eigenvalue of has Moreover, there is a positive vector with Any other vector with this property is a scalar multiple of Furthermore, any nonnegative vector that is an eigenvector of must be a scalar multiple of

In other words, if 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

### From matrices to graphs

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

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 matrix Then we can build a graph with vertices where there is an edge from the th vertex to the th vertex if and only if

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 any vertex to any vertex, 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 is **irreducible** if its graph is strongly connected.

### The Perron–Frobenius theorem

Now we are ready to state:

**The Perron-Frobenius Theorem.** Given an irreducible nonnegative square matrix there is a positive real number called the **Perron–Frobenius eigenvalue** of such that is an eigenvalue of and any other eigenvalue of has Moreover, there is a positive vector with Any other vector with this property is a scalar multiple of Furthermore, any nonnegative vector that is an eigenvector of must be a scalar multiple of

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

Its Perron–Frobenius eigenvalue is 1, but it also has -1 as an eigenvalue. In general, Perron-Frobenius theory says quite a lot about the other eigenvalues on the circle but we won’t need that fancy stuff 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:

• Dimitrious Noutsos, Perron Frobenius theory and some extensions, 2008. (Includes proofs of the basic theorems.)

• V. S. Sunder, Perron Frobenius theory, 18 December 2009. (Includes applications to graph theory, Markov chains and von Neumann algebras.)

• Stephen Boyd, Lecture 17: Perron Frobenius theory, Winter 2008-2009. (Includes a max-min characterization of the Perron–Frobenius eigenvalue and applications to Markov chains, economics, population growth and power control.)

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:

• Wikipedia, Perron–Frobenius theorem.

It’s got a lot of information.

### Irreducible Dirichlet operators

Now comes the payoff. We saw how to get a Dirichlet operator 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 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 ! The result is a nonnegative matrix

where is some large number. This matrix has the same eigenvectors as The off-diagonal matrix entries of are the same as those of so is nonzero for exactly when the graph we started with has an edge from to So, for the graph will have an directed edge going from to precisely when our original graph had an edge from to And that means that if our original graph was connected, will be strongly connected. Thus, by definition, the matrix is irreducible!

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

**Lemma.** Suppose is the Dirichlet operator coming from a connected finite simple graph with edges labelled by positive numbers. Then the eigenvalues of are real. Let be the largest eigenvalue. Then there is a positive vector with Any other vector with this property is a scalar multiple of Furthermore, any nonnegative vector that is an eigenvector of must be a scalar multiple of

*Proof.* The eigenvalues of are real since is self-adjoint. Notice that if is the Perron–Frobenius eigenvalue of and

then

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

But in fact we can improve this result, since the largest eigenvalue 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 is an irreducible Dirichlet operator. Then has zero as its largest real eigenvalue. There is a positive vector with Any other vector with this property is a scalar multiple of Furthermore, any nonnegative vector that is an eigenvector of must be a scalar multiple of

*Proof.* Choose as in the Lemma, so that Since is positive we can normalize it to be a stochastic state:

Since is a Dirichlet operator, sends stochastic states to stochastic states, so

for all On the other hand,

so we must have █

What’s the point of all this? One point is that there’s a unique stochastic state that’s an **equilibrium** state: since it doesn’t change with time. It’s also **globally stable**: since all the other eigenvalues of 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 whose entry is the number labelling the edge from to if there is such an edge, and zero otherwise:

Remember how the game works. The matrix 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 whose entries are the sums of the columns of In this example it just so happens that the column sums are all 4, so and our Dirichlet operator is

We’ve set up this example so it’s easy to see that the vector has

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

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

(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:

To compare the quantum and stochastic states, consider first This is the only eigenvector that can be normalized to a stochastic state. Remember, a stochastic state must have nonnegative components. This rules out through to 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,

can be normalized to give stochastic state only if

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 be a nonnegative matrix. Show that is irreducible if and only if for all for some natural number

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 is irreducible if and only if the nonnegative operator (where 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 in stochastic mechanics assigns a number to each configuration We can make a diagonal matrix with as its diagonal entries, and by abuse of language we call this as well. Then we say is a **conserved quantity** for the Hamiltonian if the commutator vanishes.

**Puzzle 5.** Let be a Dirichlet operator. Show that is irreducible if and only if every conserved quantity for is a constant, meaning that for some we have for all (Hint: examine the proof of Noether’s theorem.)

In fact this works more generally:

**Puzzle 6.** Let be an infinitesimal stochastic matrix. Show that is an irreducible nonnegative matrix for all sufficiently large if and only if every conserved quantity for is a constant.

Great post!

Typo alert: the formulas in this sentence are missing their requisite “latex”.

Also:

Wow, thanks for catching all those errors! I fixed them. I can see at least one person read to the very end.

“…good both for stochastic mechanics and stochastic mechanics.”

Well, it’s true! But I’ll fix it anyway.

[…] And there are nice theorems that let you know when a stochastic matrix maps exactly one probability distribution to itself, based on the Perron–Frobenius theorem. […]

For puzzle 1:

Given that

and such that

Consider the case when . We get

Then as , either or is equal to 0 for every .

Now if for some , , then all are 0 except . Further if , where , is also not 0, we have all are 0 except . Since , is also 0 and so is . Therefore, if any two elements of a column in U are non zero, we have zero row in V, which implies that V is non invertible. As this is not the case, at most one element of each column in U can be non zero.

Now as

and for each j there is only one i such that is non zero, we find that this is equal to 1.

When ,

Now, for each we have one , such that . Suppose that is not equal to any of these s for any of the s. Then which is a contradiction. So, for every too, we have a unique such that is non zero, in fact 1.

We get a similar result for V.

These facts fit the definition of a permutation matrix. As a check we have from , that if , then also.

Great, I will add this argument to the book at some point, and credit you. I want to have answers to all the puzzles.

Typo:

In the third and 4th bullets in the paragraph on symmetries, the exponential terms need to be exchanged.

Thanks—fixed!

For Puzzle 2:

In Puzzle 1, only the positivity of is required to prove that is a permutation matrix.

Now, if is positive, so is , ‘s inverse. So the puzzle is reduced to puzzle 1, due to above. Therefore, a stochastic as well as unitary matrix is also a permutation matrix.

That sounds right! Thanks.

Typo:

In the section on irreducible Dirichlet operators, after ,… The off-diagonal matrix entries of T are the same as those of A. Here, A should be H.

Thanks—fixed!

Typo in puzzle 3: -> .

For Puzzle 3:

Given that T is a nonnegative matrix, we can associate a graph with it, as was done in the post.

Notice that .

If is non zero, it means that neither nor is zero, i.e. there exists an edge from vertex to and an edge from to . So , if non zero, corresponds to a directed 2-edge path from to .

Since, all elements of are nonnegative, is zero only if there is no directed 2-edge path from to . If it is non-zero, there is at least one directed 2-edge path connecting and .

Now . If non zero, there is at least one directed 2-edge path from to and a directed edge from to ; therefore a directed 3-edge path from to .

Through induction, is non zero, if there is a directed m-edge path from to .

Since, T is irreducible iff there is a directed path from every vertex to every other vertex in , we get the result that T is irreducible iff there exists a natural number m such that , so that there is at least one directed path connecting any pair of vertices.

For puzzle 4,

For checking connectedness, we are concerned only with the non diagonal terms.

Since , and have the same non-diagonal terms, if for each with , there exists a natural number m such that , then and vice versa.

So, is irreducible iff is irreducible.

Puzzle 5:

If is a conserved quantity for , then , implying that for . Now, as is a diagonal matrix, therefore for all .

If is an irreducible Dirichlet operator, then from Puzzle 4, there exists a natural number m such that for every with .

Now, assume that is not a constant. Then there exists at least one pair , for which . Then from the previous paragraph, for all , which contradicts the fact that is an irreducible Dirichlet operator.

Conversely, if we assume that the only s for which , are constant, then there has to be at least one for which ; otherwise need not be equal to .

Puzzle 6:

In both Puzzles 4 and 5, we did not have to use the self-adjointness of , so it could have been an infinitesimal stochastic matrix, following the same definition of irreducibility. So, we get the required result.

In case anyone cares: I have just edited all Arjun’s answers here and added them to Section 16.10 of the book based on these blog articles. The book is getting close to done!

[…] Introduction to Dirichlet operators and the Perron–Frobenius theorem, Network Theory Part 20 […]