Notebooks · posts/make-power-iteration-converge-on-a-tied-pair

Make power iteration converge on a tied pair

Adam Zettel · September 25, 2026 · written with an agent

Power iteration multiplies a vector by $A$ again and again and finds the eigenvalue of largest magnitude. The matrix above has two, $+ 2$ and $- 2$ , of the same magnitude, and the iterate swaps its two entries every step forever. Write shifted_power so that the shift $s$ breaks the tie: iterate with $A + s I$ , whose eigenvalues are $λ + s$ .

A = (0220), λ = \pm 2 : v_{k + 1} = \frac{( A + s I ) v _{k}}{∥ ( A + s I ) v _{k} ∥}

Write $v_{0}$ in the eigenvectors, $v_{0} = a u_{+} + b u_{-}$ . After $k$ steps $A^{k} v_{0} = 2^{k} (a u_{+} + (- 1)^{k} b u_{-})$ : the two parts stay the same size, and the sign of one flips each step. From $(1, 0.3)$ the normalized iterate alternates between $(0.958, 0.287)$ and $(0.287, 0.958)$ , and its Rayleigh quotient $v^{T} A v$ is 1.101, which is neither eigenvalue.

$A + s I$ has the same eigenvectors, with eigenvalues $2 + s$ and $- 2 + s$ . With $s = 1$ those are 3 and $- 1$ , so the $u_{+}$ part wins by a factor of 3 per step; with $s = - 1$ they are 1 and $- 3$ , and $u_{-}$ wins. The Rayleigh quotient of the original $A$ then gives the eigenvalue itself.

The second matrix, $(12 2 - 1)$ , has eigenvalues $\pm 5$ , again a tie. The expected vectors are numpy.linalg.eigh's (posts/refs/make-power-iteration-converge-on-a-tied-pair.py), signed so that the first entry is positive; the function must return its vector signed the same way.

Look inside this program

Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.

This is a problem: its tests fail until the functions in it are written. Edit a cell and run it to try; the cells below it show whether the tests pass.

Shift+Enter in a cell runs it and moves to the next. Running a cell runs every cell above it too, as one program.

[1]lines 30–97

A_TIE = [[0.0, 2.0], [2.0, 0.0]]
B_TIE = [[1.0, 2.0], [2.0, -1.0]]
ITERS = 60

#| The unit vector power iteration with $A + sI$ reaches after `iters` steps from
#| $(1, 0.3)$, signed so its first entry is positive. As written it ignores the
#| shift $s$.
def shifted_power(A: Arr, s, iters) {
    v = [1.0, 0.3]
    for k to iters {
        w = zeros(2)
        for i to 2 {
            w[i] = A[i, 0] * v[0] + A[i, 1] * v[1]
        }
        v = w / sqrt(w[0] * w[0] + w[1] * w[1])
    }
    if v[0] < 0.0 {
        v = -v
    }
    return v
}

#| The Rayleigh quotient $v^{\mathsf T} A v$ of a unit vector v.
def rayleigh(A: Arr, v: Arr) {
    q = 0.0
    for i to 2 {
        for j to 2 {
            q = q + v[i] * A[i, j] * v[j]
        }
    }
    return q
}

v_plain = shifted_power(A_TIE, 0.0, ITERS)
show v_plain
show rayleigh(A_TIE, v_plain)
# the eigenvalues 2 + s and -2 + s of A_TIE + sI, for s = 1 and then s = -1
tie_shift = 1.0
shifted_eigs = [A_TIE[0, 1] + tie_shift, -A_TIE[0, 1] + tie_shift, A_TIE[0, 1] - tie_shift, -A_TIE[0, 1] - tie_shift]
show shifted_eigs

test "shift +1 finds eigenvalue 2, vector (1, 1) / sqrt 2" {
    v = shifted_power(A_TIE, 1.0, ITERS)
    assert_near(v[0], 0.7071067811865475, 1.0e-12)
    assert_near(v[1], 0.7071067811865475, 1.0e-12)
    assert_near(rayleigh(A_TIE, v), 2.0, 1.0e-12)
}
test "shift -1 finds eigenvalue -2, vector (1, -1) / sqrt 2" {
    v = shifted_power(A_TIE, -1.0, ITERS)
    assert_near(v[0], 0.7071067811865475, 1.0e-12)
    assert_near(v[1], -0.7071067811865475, 1.0e-12)
    assert_near(rayleigh(A_TIE, v), -2.0, 1.0e-12)
}
test "on [[1, 2], [2, -1]] shift +1 finds sqrt 5 = 2.2360680 with numpy's vector" {
    v = shifted_power(B_TIE, 1.0, ITERS)
    assert_near(v[0], 0.8506508083520399, 1.0e-12)
    assert_near(v[1], 0.5257311121191335, 1.0e-12)
    assert_near(rayleigh(B_TIE, v), 2.23606797749979, 1.0e-12)
}
test "and shift -1 finds -sqrt 5" {
    v = shifted_power(B_TIE, -1.0, ITERS)
    assert_near(v[0], 0.5257311121191335, 1.0e-12)
    assert_near(v[1], -0.8506508083520399, 1.0e-12)
    assert_near(rayleigh(B_TIE, v), -2.23606797749979, 1.0e-12)
}

# SPDX-License-Identifier: MIT OR Apache-2.0
# SPDX-FileCopyrightText: 2026 The Viv authors

A_TIE = [[0.0, 2.0], [2.0, 0.0]]
B_TIE = [[1.0, 2.0], [2.0, -1.0]]
ITERS = 60

#| The unit vector power iteration with $A + sI$ reaches after `iters` steps from
#| $(1, 0.3)$, signed so its first entry is positive. As written it ignores the
#| shift $s$.
def shifted_power(A: Arr, s, iters) {
    v = [1.0, 0.3]
    for k to iters {
        w = zeros(2)
        for i to 2 {
            w[i] = A[i, 0] * v[0] + A[i, 1] * v[1]
        }
        v = w / sqrt(w[0] * w[0] + w[1] * w[1])
    }
    if v[0] < 0.0 {
        v = -v
    }
    return v
}

#| The Rayleigh quotient $v^{\mathsf T} A v$ of a unit vector v.
def rayleigh(A: Arr, v: Arr) {
    q = 0.0
    for i to 2 {
        for j to 2 {
            q = q + v[i] * A[i, j] * v[j]
        }
    }
    return q
}

v_plain = shifted_power(A_TIE, 0.0, ITERS)
show v_plain
show rayleigh(A_TIE, v_plain)
# the eigenvalues 2 + s and -2 + s of A_TIE + sI, for s = 1 and then s = -1
tie_shift = 1.0
shifted_eigs = [A_TIE[0, 1] + tie_shift, -A_TIE[0, 1] + tie_shift, A_TIE[0, 1] - tie_shift, -A_TIE[0, 1] - tie_shift]
show shifted_eigs

test "shift +1 finds eigenvalue 2, vector (1, 1) / sqrt 2" {
    v = shifted_power(A_TIE, 1.0, ITERS)
    assert_near(v[0], 0.7071067811865475, 1.0e-12)
    assert_near(v[1], 0.7071067811865475, 1.0e-12)
    assert_near(rayleigh(A_TIE, v), 2.0, 1.0e-12)
}
test "shift -1 finds eigenvalue -2, vector (1, -1) / sqrt 2" {
    v = shifted_power(A_TIE, -1.0, ITERS)
    assert_near(v[0], 0.7071067811865475, 1.0e-12)
    assert_near(v[1], -0.7071067811865475, 1.0e-12)
    assert_near(rayleigh(A_TIE, v), -2.0, 1.0e-12)
}
test "on [[1, 2], [2, -1]] shift +1 finds sqrt 5 = 2.2360680 with numpy's vector" {
    v = shifted_power(B_TIE, 1.0, ITERS)
    assert_near(v[0], 0.8506508083520399, 1.0e-12)
    assert_near(v[1], 0.5257311121191335, 1.0e-12)
    assert_near(rayleigh(B_TIE, v), 2.23606797749979, 1.0e-12)
}
test "and shift -1 finds -sqrt 5" {
    v = shifted_power(B_TIE, -1.0, ITERS)
    assert_near(v[0], 0.5257311121191335, 1.0e-12)
    assert_near(v[1], -0.8506508083520399, 1.0e-12)
    assert_near(rayleigh(B_TIE, v), -2.23606797749979, 1.0e-12)
}

# SPDX-License-Identifier: MIT OR Apache-2.0
# SPDX-FileCopyrightText: 2026 The Viv authors