Codex @codex  0

A scalar

λ

is an eigenvalue of an

n \times n

P

if there is a nonzero vector

v

such that

P v = λ v, v \neq = 0 .

Any such vector is an eigenvector corresponding to

λ

. The requirement that an eigenvector be nonzero is essential: the zero vector would satisfy the equation for every scalar and would convey no information.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Digital systems, linear algebra, introduction to formal proof (resit) / 5 / d / Solution 2026-10-31

For

1 = (1, 1, 1)^{T}

, the entries of

P^{T} 1

are the column sums of

P

. Hence

P^{T} 1 = 111 = 1,

1

is an eigenvalue of

P^{T}

, with eigenvector

1

The determinant is unchanged by matrix transposition, so

det (P - I) = det ((P - I)^{T}) = det (P^{T} - I) = 0.

Thus

P - I

has a nontrivial null space, giving

1 is also an eigenvalue of P .

(3)

The same argument with

λ I

shows that a matrix and its transpose have the same characteristic polynomial. It does not say that they have the same eigenvectors: here

P 1 = (0.9, 1.2, 0.9)^{T} \neq = 1

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Digital systems, linear algebra, introduction to formal proof (resit) / 6 / a / Solution 2026-10-31

For a real

m \times n

A

, the row space is the linear span of its rows in

R^{n}

. The column space is the linear span of its columns in

R^{m}

, equivalently

{A x : x \in R^{n}}

. The null space is

ker A = {x \in R^{n} : A x = 0} .

The matrix rank is the dimension of the column space, which equals the dimension of the row space. In particular,

rank A = dim Row (A) = dim Col (A), dim ker A = n - rank A .

The last equality is the rank-nullity theorem.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Digital systems, linear algebra, introduction to formal proof (resit) / 6 / c / Solution 2026-10-31

Let

c_{1}, \dots, c_{4}

be the original columns. The first three are linearly independent: restricting them to rows 2, 3 and 4 gives the triangular matrix

100110011,

whose determinant is one. Also

c_{4} = c_{1} - c_{2} + c_{3}

, so a basis for the column space is

B_{col} = ⎩ ⎨ ⎧ 11001, 11100, 10110 ⎭ ⎬ ⎫ .

These are columns of the original matrix. Taking columns of its reduced row echelon form would generally give the wrong column space.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof / 4 / c / Solution 2026-10-31

No. Take the one-by-one matrices

A = [1]

B = [- 1]

. Both column spaces are

C = R

, whereas

A + B = [0]

has column space

{0}

. More generally, taking

B = - A

cancels any nonzero column space. One always has

Col (A + B) \subseteq C

, because each sum column lies in the vector subspace

C

, but equality can fail through cancellation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof / 5 / a / Solution 2026-10-31

For square matrices of the same size,

det (A B) = det (A) det (B) .

For an upper or lower triangular matrix

T

, its determinant is the product of its diagonal entries:

det (T) = i = 1 \prod n t_{ii} .

These formulas include singular matrices and zero diagonal entries.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof / 5 / d / Solution 2026-10-31

Write the determinant in its Leibniz formula for determinants, where

S_{n}

is the set of permutations of

{1, \dots, n}

det (A) = \sum_{σ \in S_{n}} sgn (σ) \prod_{i = 1}^{n} a_{i, σ (i)} .

The permutation sign is justified by the given row-interchange property: a permutation matrix is obtained from the identity matrix by row interchanges, and every interchange changes its determinant by a factor

- 1

. Reversing a sequence of interchanges constructs the inverse permutation with the same number of interchanges. Consequently

sgn (σ^{- 1}) = sgn (σ)

. The Leibniz formula for determinants can itself be obtained by expanding the rows multilinearly in the standard basis: repeated selected coordinate rows contribute zero, and the remaining terms are precisely these signed permutation matrices.

Since

(A^{T})_{ij} = a_{ji}

, the same formula gives

det (A^{T}) = \sum_{σ \in S_{n}} sgn (σ) \prod_{i = 1}^{n} a_{σ (i), i} .

Reindex the product with

j = σ (i)

and reindex the sum with

τ = σ^{- 1}

. Both reindexings are bijections, so

det (A^{T}) = \sum_{τ \in S_{n}} sgn (τ) \prod_{j = 1}^{n} a_{j, τ (j)} = det (A) .

(3)

Thus $det (A) = det (A^{T})$ for every real square matrix, including singular matrices. This proof does not assume the analogous column-operation rules in order to establish the transpose identity.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof / 6 / a / Solution 2026-10-31

An eigenvalue and eigenvector pair

(λ, v)

for a square matrix

A

satisfies

A v = λ v, v \neq = 0.

The scalar

λ

and the coordinates of

v

belong to the chosen field, usually

R

C

. The nonzero condition is essential: the zero vector satisfies the equation for every

λ

and therefore cannot define an eigenvalue.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof / 6 / d / Solution 2026-10-31

Interpret “distinct eigenvalues” as $n$ pairwise distinct eigenvalues in the chosen field. Select a nonzero eigenvector

z_{i}

for each. A single nonzero vector is linearly independent. Suppose inductively that

z_{1}, \dots, z_{k}

are linearly independent. If adding

z_{k + 1}

made the set linearly dependent, its nontrivial relation would have a nonzero coefficient of

z_{k + 1}

, since otherwise it would contradict the induction hypothesis. Solving for

z_{k + 1}

would place it in the linear span of the first

k

eigenvectors.

Part (c) would then force

λ_{k + 1} = λ_{i}

for some

i \leq k

, contradicting pairwise distinctness. Mathematical induction therefore proves that all $n$ selected eigenvectors are linearly independent, forming a basis. If the field is

R

, the assertion requires

n

real eigenvalues; a real matrix can instead have nonreal eigenvalues and a eigenvector basis over the complex numbers.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof / 6 / e / Solution 2026-10-31

For

A

, the triangular matrix formula gives the characteristic polynomial

det (t I - A) = (t - 1) (t - 3) (t - 2) .

The three eigenvalues are distinct, so part (d) already proves the existence of an eigenvector basis. Explicit choices, ordered by eigenvalues

1, 3, 2

, are

(1, 0, 0)^{T}, (1, 1, 0)^{T}, (2, - 1, 1)^{T} .

Their column matrix has determinant one, and direct multiplication gives respectively one, three and two times the indicated vector.

For

B

, expansion along the last row gives

det (t I - B) = (t - 3) ((t - 3)^{2} - 1) = (t - 3) (t - 4) (t - 2) .

(3)

Again the three eigenvalues are distinct. An explicit eigenvector basis, ordered by eigenvalues

4, 2, 3

, is

(1, 1, 0)^{T}, (1, - 1, 0)^{T}, (0, - 1, 1)^{T} .

(4)

Its column matrix has determinant

- 2 \neq = 0

. In particular,

B

's diagonal entries are not its eigenvalues: it is not a triangular matrix.

Finally

C = I_{3}

, so every nonzero vector is an eigenvector with eigenvalue one. Choose the standard basis $e_{1}, e_{2}, e_{3}$ . These are linearly independent even though their eigenvalues coincide. Distinct eigenvalues are sufficient for an eigenvector basis, and are not necessary.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4 / a / i / Solution 2026-10-31

Use the source's type Matrix a = [[a]]. For its nonempty rectangular matrices, the number of rows and the first row's length determine the dimensions:

dimensions :: Matrix a -> (Int,Int)
dimensions rows = (length rows, length (head rows))

addMat :: Num a => Matrix a -> Matrix a -> Matrix a
addMat a b
  | dimensions a /= dimensions b = error "addMat: incompatible sizes"
  | otherwise = [[x + y | (x,y) <- zip r s]
                         | (r,s) <- zip a b]

The outer list comprehension pairs corresponding rows; the inner one pairs corresponding entries. Checking both dimensions before using zip prevents silent truncation. Thus the result has entries $c_{ij} = a_{ij} + b_{ij}$ , the definition of matrix addition. The Num constraint supplies the addition operation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4 / b / i / Solution 2026-10-31

A recursive transpose removes the first column, then transposes the remaining columns:

transpose :: Matrix a -> Matrix a
transpose [] = []
transpose ([] : _) = []
transpose rows = map head rows : transpose (map tail rows)

The internal recursive calls eventually reach rows of length zero, even though the original input has positive dimensions; the second equation handles this terminating case. Rectangularity ensures that the rows become empty together, so no head or tail is applied to an empty row in the third equation. The output is an $n \times m$ matrix with entry $b_{ji} = a_{ij}$ . The element type is unrestricted.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 3 / e / Solution 2026-10-31

Accumulate the product of the

2 \times 2

matrices from left to right, which matches forward linked list traversal.

PROCEDURE cf2rat(f: fraction; VAR n, d: INTEGER);
VAR p: fraction; a, b, c, e, x: INTEGER;
BEGIN
  a := 1; b := 0; c := 0; e := 1;
  p := f;
  WHILE p # NIL DO
    x := p.head;
    a, b, c, e := a*x+b, a, c*x+e, c;
    p := p.tail
  END;
  n := a; d := c
END cf2rat;

The four-value assignment is simultaneous, as permitted by the source. With

M (x) = (x 1 10)

, the loop invariant after reading the prefix

x_{0}, \dots, x_{t - 1}

(a c b e) = M (x_{0}) \dots M (x_{t - 1}),

with the empty product initialized to the identity matrix. Multiplication on the right by

M (x)

produces exactly the four assignments above. The associativity of matrix multiplication allows this left-to-right accumulation even though the recursive conversion groups operations from the right.

At completion, the first column is the numerator/denominator pair for the whole continued fraction: the last factor sends

(1, 0)^{T}

(x_{n}, 1)^{T}

, and each earlier factor applies the recurrence from part (d). The vector

(1, 0)^{T}

is an algebraic device, not a finite input ratio requiring division by zero. For a nonempty list the resulting

c

is positive; for a singleton it is

1

. The product has determinant

(- 1)^{n + 1}

, so its first-column entries are coprime. Return $(a, c)$ in linear node-processing time and $O (1)$ auxiliary space, without changing the list.

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 3 / c / Solution 2026-10-31

First enumerate each possible row, then choose one row from each row's alternatives:

expand :: Matrix [a] -> [Matrix a]
expand = cp . map cp

The inner Cartesian product converts one row of cell choices into its possible rows; the outer product combines those rows into whole matrices. Every assignment is represented exactly once when each cell's alternatives are distinct. Empty cell domains yield no grids, and an empty matrix yields the singleton list containing the empty matrix.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 4 / b / i / Solution 2026-10-25

The product

A B

m \times p

, so multiplying it by the

p \times q

C

gives an $m \times q$ matrix. The product

BC

n \times q

, so multiplying it on the left by the

m \times n

A

also gives an $m \times q$ matrix. Both multiplications have matching inner dimensions.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 5 / b / Solution 2026-10-25

Associativity of matrix multiplication identifies

(q_{i}^{T} x) q_{i} = q_{i} (q_{i}^{T} x) = (q_{i} q_{i}^{T}) x

. Thus each matrix $P_{i} = q_{i} q_{i}^{T}$ has the required action and

x = \sum_{i} P_{i} x

Consequently

(\sum_{i} P_{i} - I_{n}) x = 0

for every

x

. Taking

x

successively as the standard basis vectors shows that every column of this difference is zero. Hence $\sum_{i = 1}^{n} P_{i} = I_{n}$ . Equality on one selected vector would not suffice; here it holds on all vectors.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 5 / c / Solution 2026-10-25

Using the unit length of

q_{i}

P_{i}^{2} = q_{i} q_{i}^{T} q_{i} q_{i}^{T} = q_{i} (q_{i}^{T} q_{i}) q_{i}^{T} = q_{i} q_{i}^{T} = P_{i} .

Then ordinary matrix expansion gives

(I_{n} - P_{i})^{2} = I_{n} - 2 P_{i} + P_{i}^{2} = I_{n} - P_{i}

. Both $P_{i}$ and its complementary matrix are projectors. The second calculation in fact holds for every idempotent matrix, without requiring the matrix to equal its transpose.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 5 / f / i / Solution 2026-10-25

For a sum of mutually orthogonal projectors, orthonormality gives

q_{i}^{T} q_{j} = 0

for

i \neq = j

and one for

i = j

. Therefore

P_{i} P_{j} = q_{i} (q_{i}^{T} q_{j}) q_{j}^{T}

equals zero for different indices and

P_{i}

for equal indices. Expanding the finite sum yields

\overline{P}_{k}^{2} = \sum_{i = 1}^{k} \sum_{j = 1}^{k} P_{i} P_{j} = \sum_{i = 1}^{k} P_{i} = \overline{P}_{k} .

Thus every stated partial sum is a projector. Its image of a linear map is the span of the first

k

orthonormal set of vectors; arbitrary sums of idempotent matrices would not have this conclusion.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 6 / a / v / Solution 2026-10-25

The iteration matrix has eigenvalues $0, - 1/2, 1/2$ : expanding its characteristic polynomial down the first column leaves the triangular two-by-two block with diagonal entries

- 1/2, 1/2

. The distinct eigenvalues ensure diagonalizability. Thus its spectral radius is

1/2 < 1

The previous bound gives

∥ f_{n} ∥ \leq 2^{- n} ∥ f_{0} ∥ \to 0

, so the Gauss-Seidel iteration converges for every initial guess under the stated diagonalization. Its limit is the exact solution

(1, 1, - 1)^{T}

. Since

e_{n} = S f_{n}

, a fixed matrix also sends this transformed error to zero; its operator norm can account for any amplification in the original coordinates.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof resit / 4 / b / ii / Solution 2026-10-25

The independent-column representation gives

T (x) = c_{1} (x_{1} + 3 x_{3}) + c_{2} (x_{2} + 2 x_{4})

. Thus a vector lies in the kernel of a linear map represented by this matrix precisely when

x_{1} = - 3 x_{3}

and

x_{2} = - 2 x_{4}

. Writing the two free coordinates separately gives

x = x_{3} - 3 010 + x_{4} 0 - 2 01 .

The two displayed vectors are linearly independent, so they form a basis of the kernel. Its dimension two also agrees with the rank-nullity theorem,

4 = 2 + 2