## Matrix Operations

### June 22, 2010

Our Standard Prelude provides a matrix datatype with create, lookup and setting operations. In today’s exercise we extend the matrix datatype with some mathematical operations: sum two matrices, multiply a matrix by a scalar, multiply two matrices, and transpose a matrix.

• Addition of two matrices is done by adding elements in corresponding positions, assuming identical dimensions. For example: $\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} + \begin{pmatrix} 2 & 3 & 4 \\ 3 & 4 & 5 \end{pmatrix} = \begin{pmatrix} 3 & 5 & 7 \\ 7 & 9 & 11 \end{pmatrix}$

• Multiplying a scalar times a matrix is done by multiplying the scalar times each element in turn. For example: $2 \times \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} = \begin{pmatrix} 2 & 4 & 6 \\ 8 & 10 & 12 \end{pmatrix}$

• The product of an m×n matrix A and an n×p matrix B is the m×p matrix C whose entries are defined by $C_{i,j} = \sum_{k=0}^{n-1} A_{i,k} \times B_{k,j}$. For example: $\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} \times \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 6 \end{pmatrix} = \begin{pmatrix} 14 & 20 & 26 & 32 \\ 32 & 47 & 62 & 77 \end{pmatrix}$

• The transpose of a matrix interchanges the rows and columns of a matrix. For example: $\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}^{T} = \begin{pmatrix}1 & 4 \\ 2 & 5 \\ 3 & 6 \end{pmatrix}$

Your task is to write functions that perform the four matrix operations described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 12 Responses to “Matrix Operations”

1. […] Praxis – Matrix Operations By Remco Niemeijer In today’s Programming Praxis exercise our task is to implement four common matrix operations. The provided […]

2. Remco Niemeijer said

add :: Num a => [[a]] -> [[a]] -> [[a]]
add = zipWith $zipWith (+) scale :: Num a => a -> [[a]] -> [[a]] scale = map . map . (*) transpose :: [[a]] -> [[a]] transpose [] = [] transpose xs = foldr (zipWith (:)) (repeat []) xs mult :: Num a => [[a]] -> [[a]] -> [[a]] mult a b = [map (sum . zipWith (*) r)$ transpose b | r <- a]

3. Here’s my Java solution.

@Remco,

Your Haskell solution is gorgeous (its simplicity astounds me). I’ll hopefully be able to churn out solutions like that in Haskell soon! =)

4. Remco Niemeijer said

@Elvis Montero:

Thanks. Best of luck with learning Haskell. I can highly recommend it :)

5. Paul Carleton said

@Remco,

6. Geir S said

;;; A scheme solution. Nothing like the beauty of the haskell one though ;-)

;; Q1
(cond ((or (null? m1) (null? m2)) ‘())
(else (cons (sum-list (car m1) (car m2))

;; Q1 helper
(define (sum-list l1 l2)
(cond ((or (null? l1) (null? l2)) ‘())
(else (cons (+ (car l1) (car l2))
(sum-list (cdr l1) (cdr l2))))))

;; Q2
(define (scale s m)
(letrec ((scale* (lambda (m)
(cond ((null? m) ‘())
(else (cons (mul-list s (car m))
(scale* (cdr m))))))))
(scale* m)))

;; Q2 helper
(define (mul-list s l)
(letrec ((mul-list* (lambda (l)
(cond ((null? l) ‘())
(else (cons (* s (car l))
(mul-list* (cdr l))))))))
(mul-list* l)))

;; Q3
(define (X A B)
(cond ((null? A) ‘())
(else (cons (psum (car A) B)
(X (cdr A) B)))))

;; Q3 helper – genereate list of cross-sums
(define (psum l m)
(letrec ((psum* (lambda ™
(cond ((null? tm) ‘())
(else (cons (xs l (car tm))
(psum* (cdr tm))))))))
(psum* (transpose m))))

;; Q3 helper – multiply each element and sum result
(define (xs l1 l2)
(cond ((or (null? l1) (null? l2)) 0)
(else (+ (* (car l1) (car l2)) (xs (cdr l1) (cdr l2))))))

;; Q4
(define (transpose m)
(cond ((null? (car m)) ‘())
(transpose (list-of-tails m))))))

;; Q4 helper
(cond ((null? m) ‘())
(else (cons (car (car m))

;; Q4 helper
(define (list-of-tails m)
(cond ((null? m) ‘())
(else (cons (cdr (car m))
(list-of-tails (cdr m))))))

7. Geir S said

bah.. indents lost :-(

one with proper indents on pocoo….

http://paste.pocoo.org/show/nZhGWlzvWmDhV9pRV5im/

8. erislover said

Geir S: list-of-heads is just (map car m)

9. erislover said

Interestingly I realized after writing it that I duplicated the Haskell version above in Scheme, though I put scalar multiplication into matrix multiplication. I have such a hard time reading Haskell that I couldn’t notice it before! No error checking. A matrix is a list of lists.

(define transpose
(λ(l)
(if (empty? (first l))
empty
(cons (map first l)
(transpose (map rest l))))))

(λ(one two)
(map (λ(x y)
(map + x y))
one two)))

(define times
(λ(one two)
(let ((sum (λ(list)
(foldl + 0 list))))
(if (number? one)
(map (λ(x) (map (λ(y) (* one y)) x)) two)
(let ((two (transpose two)))
(map (λ(x) (map (λ(y) (sum (map * x y))) two)) one))))))

10. Eric Pierce said

-- Matrix.hs
--
-- Defines a Matrix data type and operations upon Matrices

data Matrix a = Matrix [[a]]
deriving (Show, Eq)

--
--   > addMatrices (Matrix [[1,2,3], [4,5,6]]) (Matrix [[2,3,4], [3,4,5]])
--   Matrix [[3,5,7], [7,9,11]]
--
addMatrices :: (Num a) => Matrix a -> Matrix a -> Matrix a
addMatrices (Matrix m1) (Matrix m2) = Matrix $zipWith (zipWith (+)) m1 m2 -- Multiply a matrix by a scalar -- -- > multScalar 2 (Matrix [[1,2,3], [4,5,6]]) -- Matrix [[2,4,6], [8,10,12]] -- multScalar :: (Num a) => a -> Matrix a -> Matrix a multScalar x (Matrix m) = Matrix$ map (map (x*)) m

-- Multiply two matrices together
--
--   > multMatrices (Matrix [[1,2,3], [4,5,6]]) (Matrix [[1,2,3,4], [2,3,4,5], [3,4,5,6]])
--   Matrix [[14,20,26,32],[32,47,62,77]]
--
multMatrices :: (Num a) => Matrix a -> Matrix a -> Matrix a
multMatrices (Matrix m1) (Matrix m2) = Matrix $[ map (multRow r) m2t | r <- m1 ] where (Matrix m2t) = transposeMatrix (Matrix m2) multRow r1 r2 = sum$ zipWith (*) r1 r2

-- Transpose a matrix
--
--   > transposeMatrix (Matrix [[1,2,3], [4,5,6]])
--   Matrix [[1,4], [2,6], [3,6]]
--
transposeMatrix :: Matrix a -> Matrix a
transposeMatrix (Matrix m) = Matrix (zipList m)

-- Zip together a list of lists. The result is truncated to the length of the
-- shortest list. This is like the builtin zip function, except it can zip
-- together an arbitrary number of lists.
zipList :: [[a]] -> [[a]]
zipList lists
-- Base cases: there are no lists, or any sub-list is empty
| length lists == 0          = []
| any ((==0) . length) lists = []
-- Take the head from each sub-list and recurse with the tails
| otherwise                  = map head lists : zipList (map tail lists)


Not nearly as sexy as @Remco’s, partly because I used a Matrix data type that complicated things somewhat unnecessarily. I wrote zipList from scratch before remembering there was a ‘transpose’ function in Data.List, but overall this was a good learning experience. I remember back when I was into C++, and I wrote some matrix classes–the header declarations alone were longer than this :-)

11. My Python solution with convenient operators overloading, though not very effective:

class Matrix:
def __init__(self, rows):
if not isinstance(rows, list) or \
not isinstance(rows, list) or \
len(rows) == 0 or len(rows) == 0:
raise ValueError
self.rows, self.cols = len(rows), len(rows)
for row in rows:
if len(row) != self.cols:
raise ValueError
self.m = list(map(list, rows))

def __repr__(self):
return '\n'.join(map(str, self.m))

data = []
for row1, row2 in zip(self.m, other.m):
data.append(list(map(lambda a, b: a + b, row1, row2)))
return Matrix(data)

def __mul__(self, other):
if isinstance(self, Matrix) and isinstance(other, Matrix):
return self.matrix_mult(other)
else:
return self.scalar_mult(other)

def __rmul__(self, other):
if isinstance(self, Matrix) and isinstance(other, Matrix):
return self.matrix_mult(other)
else:
return self.scalar_mult(other)

def matrix_mult(self, other):
if self.cols != other.rows:
raise ValueError
data = []
for i in range(self.rows):
row = []
for j in range(other.cols):
row.append(sum(map(lambda a: a*a, zip(self.m[i], map(lambda l: l[j], other.m)))))
data.append(row)
return Matrix(data)

def scalar_mult(self, scalar):
data = []
for row in self.m:
data.append(list(map(lambda x: x * scalar, row)))
return Matrix(data)

def transpose(self):
data = []
for i in range(self.cols):
data.append(list(map(lambda x: x[i], self.m)))
return Matrix(data)

12. Will said

Scheme solution:

(define (add mat1 mat2) (map (lambda (x y) (map + x y)) mat1 mat2))

(define (scale n mat) (map (lambda (y) (map (lambda (x) (* n x)) y)) mat))

(define (transpose mat) (apply map list mat))

(define (mult mat1 mat2)
(map
(lambda (row) (apply map (lambda column (apply + (map * row column))) mat2))
mat1))