Homepage › Solution manuals › Dimitris Bertsimas › Introduction to Linear Optimization › Exercise 4.31 (Unit eigenvectors of stochastic matrices)

Exercise 4.31 (Unit eigenvectors of stochastic matrices)

We say that an n × n matrix P,with entries P ij , is stochastic if all of its entries are nonnegative and

∑ i = 1 n P ij = 1 , ∀ ⁡ i ,

that is, the sum of the entries of each row is equal to 1. Use duality to show that if P is a stochastic matrix, then the system of equations

p ′ P = p ′ , p ≥ 0 ,

has a nonzero solution. (Note that the vector p can be normalized so that its components sum to one. Then, the result in this exercise establishes that every finite state Markov chain has an invariant probability distribution.)

Answers

p ′ P = p ′ , p ′ ≥ 0 ⟺ p ′ ( P − I ) = 0 , p ′ ≥ 0

max ∑ ⁡ p i min 0 ′ x
p ′ ( P − I ) = 0 ⟺ dual ( P − I ) x ≥ 1
p ≥ 0

If we show that primal is infeasible, using strong duality and the fact that 0 ∈ (D) ≠ ϕ , we can show that dual optimum is + ∞ . Then there exists a p for each h such that ∑ ⁡ p i > h so ∃ ⁡ p ≠ 0 .
Let us assume otherwise and have a x ∈ primal .

( P − I ) x ≥ 1 ⟹ Px = x + 1 ⟹ Px = [ P 1 ′ x , . . . , P n ′ x ] ′

Note that ∑ ⁡ j P ij = 1 , P ij ≥ 0 . So we have:

Px ≤ [ max ( x ) , . . . , max ( x ) ] : = ρ where max(x) is the maximum element of vector x.

If i ∗ = argmax ( x ) , then it is obvious that

ρ i ∗ < ( x + 1 ) i ∗ = ( Px ) i ∗

which is a contradiction

User profile picture
2025-01-24 14:25
Comments

Let P ∈ ℝ n × n be a stochastic matrix, i.e., P ij ≥ 0 and ∑ ⁡ j = 1 n P ij = 1 for all i . We aim to show that the system

p ⊤ ⁡ P = p ⊤ ⁡ , p ≥ 0 , p ≠ 0

has a solution.

This is equivalent to finding a nonzero p ≥ 0 such that

p ⊤ ⁡ ( P − I ) = 0 .

Let A : = P ⊤ ⁡ − I . Then we seek x ≥ 0 , x ≠ 0 , with Ax = 0 .

By Farkas’ Lemma, exactly one of the following holds:

(i) Ax = 0 , x ≥ 0 , x ≠ 0 , (ii) ∃ ⁡ y ∈ ℝ n  such that  y ⊤ ⁡ A > 0 .

We will show that (ii) is not possible. Suppose y ⊤ ⁡ A > 0 , i.e.,

y ⊤ ⁡ ( P ⊤ ⁡ − I ) = ( Py − y ) ⊤ ⁡ > 0 ⇒ Py > y  (componentwise) .

But since P is stochastic, each row is a convex combination of the entries of y , so Py ≤ max ⁡ j y j . Hence, Py > y is impossible.

Thus, (ii) has no solution, and by Farkas’ Lemma, (i) holds. Therefore, there exists x ≥ 0 , x ≠ 0 such that Ax = 0 , i.e.,

( P ⊤ ⁡ − I ) x = 0 ⇒ P ⊤ ⁡ x = x ⇒ x ⊤ ⁡ P = x ⊤ ⁡ .

Hence, x ≥ 0 , x ≠ 0 is a solution to the system p ⊤ ⁡ P = p ⊤ ⁡ , p ≥ 0 . □

User profile picture
2025-05-29 08:51
Comments