SICP Exercise 2.37

sicp

Question

Suppose we represent vectors \(v=(v_i)\) as sequences of numbers, and matrices \(m=(m_{ij})\) as sequences of vectors (the rows of the matrix). For example, the matrix \[\begin{bmatrix} 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 6 \\ 6 & 7 & 8 & 9 \end{bmatrix}\] is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following:

  • (dot-product v w) returns the sum \(\sum_iv_iw_i\);
  • (matrix-*-vector m v) returns the vector \(t\), where \(t_i=\sum_jm_{ij}v_j\);
  • (matrix-*-matrix m n) returns the matrix \(p\), where \(p_{ij}=\sum_km_{ik}n_{kj}\);
  • (transpose m) returns the matrix \(n\), where \(n_{ij}=m_{ji}\).

We can define the dot product as

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

Fill in the missing expressions in the following procedures for computing the other matrix operations. (The procedure accumulate-n is defined in exercise 2.36.)

(define (matrix-*-vector m v)
  (map ⟨??⟩ m))

(define (transpose mat)
  (accumulate-n ⟨??⟩ ⟨??⟩ mat))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map ⟨??⟩ m)))

Answer

For a refresher in Matrix algebra, I highly recommend Khan Academy. But the exercise can be solved without it, since everything is well explained in the question.

So let’s begin with matrix-vector multiplication. This works by basically splitting the matrix \(m\) up into vectors \(m_0, m_1, \ldots ,m_n\) (same thing as accessing sublists in Scheme) and then creating a new vector out of all the dot-products \((m_i\cdot v)\).

(define (matrix-*-vector m v)
  (map (λ (x) (dot-product x v)) m))

Then let us continue with transpose. This basically flips a matrix by 90 degrees. If we have a matrix \(m=\begin{bmatrix}1 & 2 & 3 \\ 4 & 5 & 6\end{bmatrix}\), the transpose of that matrix will be \(n=\begin{bmatrix}1 & 4 \\ 2 & 5 \\ 3 & 6\end{bmatrix}\). Here is the code for transpose:

(define (transpose mat)
  (accumulate-n cons nil mat))

And finally, matrix-matrix multiplication. For this to work, the amount of columns in matrix \(m\) must be the equal to the number of rows in matrix \(n\). Then, to build the resulting matrix \(p\), we take the product of each row in \(m\) (which is just a vector) and the transpose of matrix \(n\). Each of these matrix-vector multiplications then makes up one row of \(p\). Here is the code that accomplishes this:

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (λ (x) (matrix-*-vector cols x)) m)))

Finally, let’s test everything by running some sample calculations:

(define m (list (list 1 2 3 4) (list 5 6 7 8) (list 9 10 11 12)))
(define n (list (list 1 1 1) (list 2 2 2) (list 3 3 3) (list 4 4 4)))
(define v (list 4 3 2 1))
(define w (list 7 8 9 10))

(dot-product v w)
(matrix-*-vector m v)
(transpose n)
(matrix-*-matrix m n)

Results:

80
(20 60 100)
((1 2 3 4) (1 2 3 4) (1 2 3 4))
((30 30 30) (70 70 70) (110 110 110))