Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Digital systems, linear algebra, introduction to formal proof / 4 / a

Table of contents
- i a
  - Solution i
- ii a
  - Solution ii
- iii a
  - Solution iii

i

Solution

By matrix multiplication,

D_{ij} = \sum_{k = 1}^{N} B_{ik} C_{kj}

. A potentially nonzero term requires

k = i

because

B

is a diagonal matrix, and

k = j

because

C

is a diagonal matrix. For

i \neq = j

these requirements cannot both hold. Thus every summand is zero and $D_{ij} = 0$ whenever $i \neq = j$ .

ii

Solution

The diagonal matrix entry is

D_{ii} = \sum_{k = 1}^{N} B_{ik} C_{ki}

. Only

k = i

can contribute, so $D_{ii} = B_{ii} C_{ii}$ . This also shows that the product is a diagonal matrix, with its diagonal obtained by entrywise multiplication of the two diagonals.

iii

Solution

Repeatedly applying the previous product rule gives

(B^{p})_{ij} = {(B_{ii})^{p} 0 i = j, i \neq = j .

Formally, the result holds for

p = 1

; multiplication by

B

preserves the zero off-diagonal matrix entries and multiplies each diagonal matrix entry by

B_{ii}

, proving the induction step.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version