CS/ECE/ME 532
Homework 1: Vectors and Matrices
1. Matrix multiplication. Settlers of Catan is the favorite game of the Green Bay Packers1
.
In this game, participants build roads, settlements, and cities by using resources such as wood,
bricks, wheat, sheep, and ore. The number of resources required for each building project are
reflected in Figure 1.
Figure 1: Building costs in Settlers of Catan
a) Write the information above in a matrix. What do the rows represent? What do the
columns represent?
b) Departing from the game somewhat, suppose resources cost $1 for each unit of wood, $2
for brick, $3 for sheep, $5 for wheat, and $8 for ore. Write this information in a vector.
Write out a matrix-vector multiplication that calculates the total cost of buying roads,
settlements, and cities.
c) Suppose you want to crush Corey Linsley by building a city, two settlements, and six
road lengths connecting them. Again using matrix multiplication, find the total resources
required to fill the order.
d) Calculate the total cost for the order (using, you guessed it, matrix multiplication)
e) Get up and running with either Matlab or Python. In your language of choice, write a
script that computes the matrix multiplications in the previous parts of this problem.
2. Let X = [x1 x2 · · · xn] ∈ R
p×n
, where xi ∈ R
p
is the ith column of X. Consider the matrix
C =
XXT
n
.
1
https://www.washingtonpost.com/news/early-lead/wp/2015/01/16/the-green-bay-packers-are-obsessed-with-settlers-of-catan/
?utm_term=.0c5c6419f03d
1 of 2
a) Express C as a sum of rank-1 matrices (i.e., columns of X times rows of XT
).
b) Assuming x1, x2, . . . , xn are linearly independent, what is the rank of C?
3. Let
X =
1 0 1 0 1
0 1 0 1 1
0 0 0 0 0
0 0 1 1 1
.
a) What is the rank of X?
b) What is the rank of XXT
?
c) Find a set of linearly independent columns in X.
2 of 2
