aMatrix Product

1. Vector-vector 1.1. Inner product 1.2. Outer product 2. Matrix-Vector and Vector-Matrix 2.1. Matrix-Vector 2.2. Vector-Matrix 3. Matrix-Matrix products 3.1. Row-column picture 3.2. Matrix-column picture 3.3. Row-matrix picture 3.4. Column-row picture 4. Summary

Question: How do we multiply two matrices?

This question may seem elementary and obvious at first sight. Let us see if this impression remains the same after the end of this section. There are several ways to understand the product of two matrices A and B of compatible dimensions. We will look at four different ways to do the same. Before we go there, we will look at matrix-vector products. Let A be an m×n matrix and B be a n×p matrix. Let C=AB. We will also define vectors a and b along the way. 1. Vector-vector 1.1. Inner product We are quite familiar with the inner product between two vectors. Given two n-dimensional vectors a and b, we have: aTb=n∑i=1aibi We know that the inner product is commutative: aTb=bTa Among all the products that we see in this section, the inner product is the only one that is a scalar. 1.2. Outer product The outer product between two vectors a and b is a matrix and is defined as: abT Let a∈Rm and b∈Rn, then abT is a m×n matrix. Let us take an example and understand what the outer product looks like. Let a=a

a1

a2

a3

T and b=a

b1

b2

b3

T, then we have: a

a1

a2

a3

a

b1

b2

b3

=a

a1b1	a1b2	a1b3
a2b1	a2b2	a2b3
a3b1	a3b2	a3b3

If we notice the matrix on the right, each row is a multiple of the row vector a

b1

b2

b3

and each column is a multiple of the column vector a

a1

a2

a3

. From this we can deduce that this matrix has rank 1. Here is an interesting fact concerning outer products.

Remark: Every matrix of unit rank can be expressed as the outer product of two vectors.

To see why this is true, start with any m×n matrix A of unit rank. If the rank is 1, then every vector in the column space of A is of the form k⋅a, where a=a

a1

⋯

am

T . Thus, each column is just some scalar multiple of a. Since there are n columns, we have n coefficients, say b1,⋯,bn, such that the ith column is bi⋅a. Therefore, the matrix A is: A=a

|		|
b1a	⋯	bna
|		|

We see that this is the outer product between the vectors a and b=a

b1

⋯

bn

: A=abT 2. Matrix-Vector and Vector-Matrix We will now turn to the situation where one of the two operands is a vector and the other a matrix: 2.1. Matrix-Vector Let A be a m×n matrix and b a column vector in Rn defined as follows: A=a

|		|
a1	⋯	an
|		|

, b=a

b1

⋮

bn

Here, ai is the ith column of A. Now, the product Ab is defined as follows: a

Ab	=b1a1+⋯+bnan
	=n∑i=1biai

The product of a matrix and a vector is a linear combination of the columns of the matrix where the coefficients of the combination come from the vector. One way to understand it is to look at what happens when the vectors come from the standard basis {e1,⋯,en}: A=a

1	2	3
4	5	6
7	8	9

, e1=a

1

0

0

, e2=a

0

1

0

, e3=a

0

0

1

We get: a

Ae1	=a 1 4 7
Ae2	=a 2 5 8
Ae3	=a 3 6 9

We see that Ae1,Ae2,Ae3 represent the first three columns of A. Now, for any arbitrary vector b=a

b1

b2

b3

T, we have b=b1e1+b2e2+b3e3. From this it follows that Ab is: a

Ab	=A(b1e1+b2e2+b3e3)
	=b1Ae1+b2Ae2+b3Ae3
	=b1⋅a 1 4 7 +b2⋅a 2 5 8 +b3⋅a 3 6 9

2.2. Vector-Matrix Let us now look at the a row vector aT and matrix B: aT=a

a1

⋯

am

, B=a

―	bT1	―
	⋮
―	bm	―

The product aTB is: a

aTB	=a1bT1+⋯+ambTm
	=m∑i=1aibTi

A vector matrix product is the linear combination of the rows of the matrix where the coefficients of the combination come from the row vector. 3. Matrix-Matrix products 3.1. Row-column picture A is expressed in terms of m row vectors. B is expressed in terms of p column vectors. a

―	aT1	―
	⋮
―	aTm	―

a

||		|
b1	⋯	bp
|		|

The ijth element of the matrix C is: Cij=aTibj This is by far the most popular form of matrix multiplication and is the first thing that we learn in high school. Each element of the matrix is represented as the inner product of two vectors. 3.2. Matrix-column picture B is expressed as a sequence of p column vectors. Aa

|		|
b1	⋯	bp
|		|

Each column of C can be represented as Abi, a linear combination of the columns of A, where the coefficients of the combination are given by the columns of B: C=a

|		|
Ab1	⋯	Abp
|		|

3.3. Row-matrix picture A is expressed as a sequence of m row vectors: a

―	aT1	―
	⋮
―	aTm	―

B Each row of the matrix C is of the form aTiB, a linear combination of the rows of B, where the coefficients of the combination are given by the rows of A: C=a

―	aT1B	―
	⋮
―	aTmB	―

3.4. Column-row picture A is expressed in terms of n column vectors. B is expressed in terms of n row vectors. a

|		|
a1	⋯	an
|		|

a

―	bT1	―
	⋮
―	bTn	―

Here is another way to multiply two matrices: C=n∑i=1aibTi Matrix C is expressed as the sum of n matrices of unit rank. Alternatively, the matrix is represented as the sum of n outer products. To see why this is true, consider an unit vector ek in the standard basis for Rp. Now, let us look the product of the RHS with ek. This is nothing but the kth column of this matrix: n∑i=1aibTiek=n∑i=1(bTiek)ai The RHS of the above expression is a linear combinations of the columns of the matrix A. The coefficients of the combination are the columns of the matrix B. This is the same as the matrix-column picture. 4. Summary The following table summarizes all that we have seen so far:

Left Operand	Right Operand	Operation	Formula
Row Vector	Column vector	Inner product	aTb
Column vector	Row vector	Outer product	abT
Matrix	Column vector	Matrix-vector product	Ab
Row vector	Matrix	Vector-matrix product	aTB
Matrix	Matrix	Row-column picture	a ― aT1 ― ⋮ ― aTm ― a || | b1 ⋯ bp | |
		Matrix-column picture	Aa | | b1 ⋯ bp | |
		Row-matrix picture	a ― aT1 ― ⋮ ― aTm ― B
		Column-row picture	a | | a1 ⋯ an | | a ― bT1 ― ⋮ ― bTn ―