SICP Exercise 2.37: Matrix Manipulation

Suppose we represent vectors v = (vi) as sequences of numbers, and matrices m = (mij) as sequences of vectors (the rows of the matrix). For example, the matrix

⎡ 1 2 3 4 ⎤
⎢ 4 5 6 6 ⎥
⎣ 6 7 8 9 ⎦

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 Σiviwi
(matrix-*-vector m v)   returns the vector t, where ti = Σjmijvj
(matrix-*-matrix m n)   returns the matrix p, where pij = Σkmiknkj
(transpose m)           returns the matrix n, where nij = mji

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)))

The formal definition of matrix-*-vector given above effectively indicates that the generated vector should contain the results of calculating the dot products of each of the rows in m and the vector v. Now as the matrix m is represented as a sequence of sequences, with each sub-sequence representing the corresponding row in the matrix, mapping across the matrix will perform an operation on each row of the sequence. So all we need to do is provide a procedure that calculates the dot product of the row and v and we have our implementation:

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

The procedure transpose needs to transform the matrix so that the rows become columns and vice versa. In other words, we need to take the first item from each row in turn and put them together, in order, into a sequence, then we take the second item from each row in turn and put them into a sequence, and so on, and put these resulting sequences together to form our transformed matrix.

Now we know that the procedure accumulate-n applies accumulate to the sequence containing the first items from each sequence in a sequence of sequences, and then cons the result onto the sequence produced by applying accumulate-n to the sequence of sequences produced by taking the tails of each of the original sequences. It just so happens that the sequence passed to accumulate in this process is the sequence we want, so all we need to do is to pass an appropriate operator and base case to accumulate-n so that it effectively turns the application of accumulate into an identity function. In this case the operator cons and the base case nil will achieve the desired effect:

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

Finally onto matrix-*-matrix. Matrix multiplication takes an a×b matrix, m, and a b×c matrix, n, and produces a new a×c matrix, p, where the value p_ij is calculated as the dot product of the i^th row of m and the j^th column of n. Handily the template we're given for matrix-*-matrix transforms the matrix n so that its rows become columns and vice versa. This means that each sub-sequence of cols will have the same length as each sub-sequence of m, and we can generate each row of the resulting matrix by taking the corresponding sub-sequence from m and applying matrix-*-vector to the matrix cols and that sub-sequence of m:

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

Okay, let's see these matrix operations in action:

> (define v (list 1 2 3))
> (define m1 (list (list 1 2 3) (list 4 5 6)))
> (define m2 (list (list 1 2) (list 3 4) (list 5 6)))
> (matrix-*-vector m1 v)
'(14 32)
> (transpose m1)
'((1 4) (2 5) (3 6))
> (matrix-*-matrix m1 m2)
'((22 28) (49 64))