Solution of second-order matrix difference equations

While browsing through my notes recently I came across this cute and not-quite trivial, but entirely elementary result. Since it doesn’t seem to be available anywhere else, I present it as blog fodder. (As usual, I will offer $.50 and a Sprite to the first person who provides a usable reference in the event that this result is already known.)

Consider the second-order matrix difference equation

x_{k+1} = Ax_k + \tilde Ax_{k-1}

with x_0, x_1 given. Some algebra shows that (e.g.)

x_2 = (A)x_1 + \tilde A x_0,

x_3 = (A^2 + \tilde A)x_1 + (A) \tilde A x_0,

x_4 = (A^3 + bsp_{1,1}[A, \tilde A])x_1 + (A^2 + \tilde A) \tilde A x_0, etc.

where the bosonic symmetrized product bsp_{j,k}[A, \tilde A] for two “species” of order (j,k) is defined as the sum of all distinguishable products with j occurences of the first species and k of the second (if j or k = 0 then the BSP is a pure power of the nontrivial species).

For example, bsp_{3,2}[A,\tilde A] equals

A A A\tilde A \tilde A + A A\tilde A A \tilde A + A A \tilde A \tilde A A + A\tilde A A A \tilde A + A\tilde A A \tilde A A

+ A \tilde A \tilde A A A + \tilde A A A A \tilde A + \tilde A A A \tilde A A + \tilde A A \tilde A A A + \tilde A \tilde A A A A.

It is not hard to verify that

bsp_{j,k}[A, \tilde A] = A \cdot bsp_{j-1,k} + \tilde A \cdot bsp_{j,k-1}[A, \tilde A]

and more generally for \ell = 0,\dots \min(j,k) that

bsp_{j,k}[A, \tilde A] = \sum_{m=0}^\ell bsp_{\ell-m,m}[A, \tilde A] \cdot bsp_{j-(\ell-m),k-m}[A, \tilde A].

The same algebra that facilitated writing down the first few terms for the difference equation quickly leads to the general solution, viz.

x_k = \left( A^{k-1} + \sum_{j=1}^{(k-1)/2 - 1} bsp_{k-2j-1,j}[A,\tilde A] + \tilde A^{(k-1)/2} \right) x_1

+ \left( A^{k-2} + \sum_{j=1}^{(k-1)/2-1} bsp_{k-2j-2,j}[A, \tilde A] \right) \tilde A x_0

for k odd, and

x_k = \left( A^{k-1} + \sum_{j=1}^{k/2 - 1} bsp_{k-2j-1,j}[A,\tilde A] \right) x_1

+ \left( A^{k-2} + \sum_{j=1}^{k/2-2} bsp_{k-2j-2,j}[A, \tilde A] + \tilde A^{k/2-1} \right) \tilde A x_0

for k even.

I used this to understand what happens when one of the internal states of a classical Bose gas becomes “more fermionic” in the sense that fewer particles can occupy that state, but the microscopic transition probabilities are otherwise unchanged. (The underlying motivation was to apply this to get a handle on the effects of some complex configurations for an older mathematically-oriented network monitoring framework in a tractable traffic regime.) It turns out that this is completely uninteresting unless the remaining “bosonic” states are close to equally likely to occur: in this event you get a slight but also quite counter-intuitive effect on the state distributions. Pseudocolor figures of the energy functions corresponding to these distributions will illustrate:

3 totally bosonic interal states

3 totally bosonic interal states. The distribution is multigeometric, and the energy is affine.

Capping the occupancy of one internal state

Capping the occupancy of one internal state

A more restrictive cap

A more restrictive cap

A "fermionic" internal state

A "fermionic" internal state

Note that the color scales differ for each figure. I think the pictures indicate how surprising the behavior of this (completely classical) “poor man’s exclusion principle” is: the effect is as unexpected as it is slight.

Hopefully posting the main result will save some other folks a head-scratch or two. I’d be interested to know if it’s applied elsewhere.

This entry was posted on Monday, November 9th, 2009 at 05:12 and is filed under Equilibrium Networks, Mathematics, Nonrandom bits. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply