Eigenvalues and repeated allocation

When the same allocation rule is applied repeatedly, multiplying a matrix once is not enough. We need to understand $B^k$. Eigenvectors identify directions whose proportions remain unchanged under the rule. They also reveal when an infinite sequence of indirect allocations has a finite total.

1 Matrix powers and invariant directions

For a square matrix $B$, an eigenvector is a nonzero vector $v$ such that $Bv=\lambda v$. The scalar $\lambda$ is its eigenvalue. Nonzero matters: zero satisfies the equation for every scalar and tells us nothing. Repeated multiplication gives $B^kv=\lambda^kv$ by induction.

A matrix is diagonalizable over $\mathbb R$ if it has a basis of real eigenvectors. Writing these as columns of an invertible matrix $P$ gives $BP=PD$ and

$$B=PDP^{-1},\qquad B^k=PD^kP^{-1},$$

where $D$ is diagonal. The formula follows by cancellation of adjacent $P^{-1}P$. Not every real matrix is diagonalizable; $\begin{pmatrix}1&1\\0&1\end{pmatrix}$ has only one independent eigenvector.

For a $2\times2$ matrix $M=\begin{pmatrix}a&b\\c&d\end{pmatrix}$, its determinant is $ad-bc$. An eigenvalue solves $\det(B-\lambda I)=0$, because a nontrivial solution of $(B-\lambda I)v=0$ exists exactly when the matrix is singular.

2 A two-department allocation example

Take

$$B=\begin{pmatrix}0&1/2\\1/2&0\end{pmatrix}.$$

Then $(1,1)$ has eigenvalue $1/2$, while $(1,-1)$ has eigenvalue $-1/2$. Equal departmental amounts decay without changing proportions; an imbalance alternates direction while shrinking. For initial amounts $u=(6,2)$,

$$u=4(1,1)+2(1,-1),\quad B^ku=4(1/2)^k(1,1)+2(-1/2)^k(1,-1).$$

At $k=1$ this is $(1,3)$, agreeing with direct multiplication. Negative eigenvalues do not imply negative entries in every predicted vector; they describe signed difference directions, not a standalone nonnegative department amount.

3 Total direct and indirect allocations

Suppose $d$ is direct cost and $x=d+Bx$ includes all indirect rounds. If $B$ is diagonalizable and all its eigenvalues satisfy $|\lambda|<1$, then $B^k\to0$ and

$$\sum_{k=0}^{\infty}B^k=(I-B)^{-1},\qquad x=(I-B)^{-1}d.$$

Proof under the stated hypothesis. Diagonalization reduces each matrix entry to finite linear combinations of $\lambda_i^k$, which tend to zero. The finite telescoping identity

$$(I-B)(I+B+\cdots+B^N)=I-B^{N+1}$$

then gives the inverse formula on taking limits; the analogous product in the other order gives a two-sided inverse. $\square$

This sufficient condition is not a characterization restricted to diagonalizable matrices: the general spectral-radius theorem also covers nondiagonalizable matrices, but is not needed for this proof.

For the matrix above and $d=(6,2)$,

$$I-B=\begin{pmatrix}1&-1/2\\-1/2&1\end{pmatrix},\qquad (I-B)^{-1}=\frac43\begin{pmatrix}1&1/2\\1/2&1\end{pmatrix}.$$

Thus $x=(28/3,20/3)$. Substitution gives $6+(1/2)(20/3)=28/3$ and $2+(1/2)(28/3)=20/3$. The totals include internal rounds; summing them is not a conservation statement about external expenditure.

Invertibility alone does not prove convergence. For $B=2I$, $I-B$ is invertible but $\sum B^k$ diverges. The algebraic fixed point $x=-d$ is not a sum of nonnegative allocations.

Establishing convergence before passing to an inverse

Suppose $B=PDP^{-1}$ with real diagonal entries $\lambda_i$ satisfying $|\lambda_i|<1$. For every $N\ge0$, finite multiplication gives

$$\sum_{k=0}^NB^k=P\operatorname{diag}\left(\frac{1-\lambda_i^{N+1}}{1-\lambda_i}\right)P^{-1}.$$

The denominators are nonzero. If $\lambda_i=0$, its positive powers are zero. Otherwise write $1/|\lambda_i|=1+\delta_i$ with $\delta_i>0$; the binomial inequality $(1+\delta_i)^k\ge1+k\delta_i$ proves $|\lambda_i|^k\to0$. Every entry of the displayed finite matrix product therefore converges to the corresponding entry of $S=P\operatorname{diag}((1-\lambda_i)^{-1})P^{-1}$. Thus the matrix series exists, before any limit is taken in the telescoping identity. Direct cancellation proves $(I-B)S=S(I-B)=I$. This proves exactly the diagonalizable real hypothesis used here, without inferring convergence from invertibility alone.

4 Graded practice

E1 Foundation. Find the eigenvalues and a real eigenbasis of $C=\begin{pmatrix}3&1\\1&3\end{pmatrix}$.

E2 Application. For $B=\begin{pmatrix}0&1/4\\1/4&0\end{pmatrix}$ and $d=(3,0)$, calculate the sum of all allocation rounds and verify the fixed-point equation.

E3 Reasoning. For a diagonalizable $B$, explain why an eigenvalue of modulus greater than or equal to 1 prevents $B^ku\to0$ for every initial vector $u$.

5 Full solutions

S1. $\det(C-\lambda I)=(3-\lambda)^2-1=(\lambda-4)(\lambda-2)$. Eigenvectors are $(1,1)$ for 4 and $(1,-1)$ for 2. They are independent, so form a basis.

S2. The inverse is $(16/15)\begin{pmatrix}1&1/4\\1/4&1\end{pmatrix}$, giving $x=(16/5,4/5)$. The first fixed-point equation reads $3+(1/4)(4/5)=16/5$ and the second reads $(1/4)(16/5)=4/5$. Eigenvalues $\pm1/4$ justify the convergent-round interpretation.

S3. Choose a nonzero eigenvector $u$ with eigenvalue $\lambda$. Then $\|B^ku\|=|\lambda|^k\|u\|$, which does not tend to zero when $|\lambda|\ge1$. A different initial vector may still decay; the conclusion concerns every initial vector.

Summary

Eigenvectors separate repeated linear rules into simple scalar recurrences. Diagonalization makes powers and convergent allocation sums transparent. Always distinguish a solvable algebraic fixed-point equation from a convergent operational process.