 Solution

ID: 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/3/a/solution

Let

U, V

n \times n

i > j

(U V)_{ij} = \sum_{k = 1}^{n} U_{ik} V_{kj} .

k < i

, then

U_{ik} = 0

. If

k \geq i

, then

k > j

, so

V_{kj} = 0

. Every summand is zero, giving

i > j ⟹ (U V)_{ij} = 0.

Thus

U V

is an upper triangular matrix. Equivalently, a potentially nonzero summand would require

i \leq k \leq j

, impossible below the diagonal.

 New to topics? Read the docs here!