3Matrices
3.1 Matrices
3.1.1 Definitions
A rectangular array of numbers is called a matrix. A matrix with rows and columns is called an ( by ) matrix. The notation for an matrix is where denotes the number or entry in the -th row and -th column. If the matrix in (3.2) is denoted , then it has rows and columns with .-
A matrix whose entries are all is called a zero matrix. It is denoted simply by , when
it is clear from the context what its numbers of rows and columns are.
- A matrix is called quadratic if it has an equal number of rows and columns. The first two matrices below are quadratic, whereas the third is not.
- The diagonal in a matrix is defined as the entries in the matrix with the same row- and column indices. Below we have a matrix with the diagonal elements marked A matrix is called a diagonal matrix, if all its entries outside the diagonal are . Below is an example of a square diagonal matrix
- A matrix is called a row vector if it has only one row. For example, is a row vector with three columns.
- A matrix is called a column vector if it has only one column. For example, is a column vector with three rows.
- The rows in a matrix are called the row vectors of the matrix. The -th row in a matrix is denoted . The matrix in (3.2) contains the row vectors
- The columns in a matrix are called the column vectors of the matrix. The -th column in a matrix is denoted Not to be confused with powers of the matrix introduced later. . The matrix in (3.2) contains the column vectors
- A row- or column vector is referred to as a vector.
- Even though we have used the notation for the -th cartesian product of , we will use henceforth to denote the set of column vectors with rows (entries). This definition is almost identical with the previous one, except that the tuple is formatted as a column vector. Illustrated by an example,
3.2 Linear maps
Let be the linear map given by the matrix
Does there exist , such that
Quite generally, can we find , such that
for arbitrary ?
Suppose you know that is a linear map and
that you have a black box giving you output if you
supply the input . How would you find
the matrix defining ?
3.3 Matrix multiplication
The row-column multiplication between a row vector
with the same number of entries is defined as
Let be an matrix and an matrix.
Then the matrix product is defined as the matrix given by the
row-column multiplication
for and .
If is an matrix and is an , then the matrix product only makes sense if
: the number of columns in must equal the number of rows in .
Suppose that
Which of the matrix products below make sense?
I have been told that my pronunciation of column in the video below is wrong. In the area of the US, where I got my PhD, people for some reason had this (Irish?)
rare pronunciation.
Suppose that
Which ones of the statements below are true?
If , then .
If , then .
3.3.1 Matrix multiplication in numpy
3.3.2 The identity matrix
Prove that the two identities in
(3.6)
are true for matrices.
3.3.3 Examples of matrix multiplication
Matrix multiplication is omnipresent in mathematics. Below we give an example, which is a baby version of Google's famous page rank algorithm.
Suppose that % of the people living in the suburbs move to the big city and
that % of the people living in the big city move to the suburbs per year.
Aiming for a model using probabilities, let us be a bit more precise.
All of the above probabilities are per year and can be illustrated in the diagram below
We are interested in predicting, using this model, how many people live
in the big city and the suburbs given that we know how many people
live in the big city, and in the suburbs to begin with i.e.,
setting the time (years).
How many people and live in the two places after the first year ()?
The population of the big city will decrease by , but there are newcomers amounting to
of the population in the suburbs. Therefore
In the same way,
Using matrix multiplication, these two equations can be written
For years, we can repeat the procedure and the result becomes
where
In general we have the formula
It seems that the distribution stabilizes around living
in the big city and living in the suburbs of the
original total population.
The matrix is an example of a stochastic matrix.
In general, a square matrix is called a stochastic matrix if its entries are
and the sum of the entries in its column vectors are .
- If you live in the suburbs, the probability that you move to the big city is ,
- If you live in the suburbs, the probability that you do not move is .
- If you live in the big city the probability that you move to the suburbs is .
- If you live in the big city the probability that you do not move is .
giving the distribution of the populations for
years.
Let us experiment a little:
In the end of Example
3.8
(above) a stochastic matrix is defined. Show that
the matrix product of two stochastic matrices is a stochastic matrix.
Suppose we have five cities connected with roads as shown below
This network has a so called incidence matrix, where city is associated with the
-th row and -th column. A in the matrix in the entry means that there is a road
from city to city , whereas a means that city and city are not connected by a road:
Here
What is the interpretation of and in general?
It turns out that the entry in the matrix exactly is
the number of paths of length from city to city .
For example, there are paths from city to city of length
corresponding to the paths . The paths from city to city of
length are and the paths of length from city to city
are .
A deeper explanation
Suppose that we have a network with cities and incidence matrix .
The general proof of the observations above in our special example, builds on the
fact that
a path of length from city to city has to end with a road from a neighboring city
to .
For every one of these neighboring cities, we may count the number of paths of length
from city .
If is the number of paths of length from city to city ,
then matrix multiplication tells us that
This number is exactly the number of paths of length from city to
city , since
only when is a neighboring city to city (and otherwise).
3.4 Matrix arithmetic
3.4.1 Matrix addition
Given an example of a non-zero matrix, such that
3.4.2 Multiplication of a number and a matrix
Does there exists a number , such that
Let be a matrix, such that
for every other matrix . Show that is a diagonal matrix of the form
where i.e., .
3.4.3 The distributive law
Let and be matrices, an matrix and an matrix. Then
Let us start by looking at .
Here it suffices to do the proof, when is a row vector and
column vectors, since
For , we may reduce to the case, where
are row vectors and a column vector, since
Both of these cases follow using the distributive law for ordinary numbers.
Suppose that and are two matrices. Is it true that
What about
3.4.4 The miraculous associative law
Let be an matrix, an matrix and an matrix. Then
We must prove that
for og . The left hand side can be written
The right hand side is
Writing the row-column multiplications in
(3.10)
, we get
Writing the row-column multiplications in
(3.11)
, we get
The rows in the sum in
(3.12)
correspond to the columns in the sum
(3.13)
.
Therefore these sums are equal and .
The associative law is true, but in computing there can be a (big)
difference in the number of multiplications in the two computations
and i.e., efficiency is not associative for
matrix multiplication. In the notation of Theorem
3.17
, computing
requires
multiplications, whereas computing requires
multiplications. If for example and , then computing
requires multiplications, whereas
computing requires multiplications!
Verify the associative law for the three matrices
by showing by explicit computation that
There is in fact a high tech explanation that the associative law for matrices holds. An explanation
that makes the calculations in the above proof superfluous and shows the raw power of
abstract mathematics: suppose that
and are linear maps.
Then and are both linear maps from , such that
for every . How does this relate to the associative law for matrix
multiplication?
3.5 The inverse matrix
Let and be matrices. Show that
and
implies that .
An matrix is called invertible, if there exists an matrix , such that
In this case, is called the inverse matrix of and denoted .
Show that a quadratic matrix with a column or row consisting entirely of zeros cannot
be invertible.
Suppose that
with . Prove that is invertible with
When is a quadratic diagonal matrix invertible? Look first at the case:
The inverse matrix can be computed in numpy:
The system of linear equations
can be rewritten using matrix multiplication to
where
Here is invertible and
One simple matrix multiplication
shows the solution we expect from
(3.14)
.
The product of two invertible matrices and is invertible and
.
We must check that
Let us check the first condition using the associative law:
where denotes the identity matrix. The condition is verified in the
same way.
Let
Compute the powers for i.e., . Now let
where .
Show that is invertible, and
Compute .
Do you see a way of generalizing this computation to
matrices with a property shared by the
matrix above?
3.5.1 Well, how do I find the inverse of a matrix?
Suppose that is a matrix. Then the inverse matrix
(if it exists) can be computed from the systems of linear
equations below.
Writing
for the first and second columns, the systems of linear equations can be written as
where
A concrete example along with a useful way of keeping track of the computation is presented in the video below.
Compute the inverse of the matrix
by employing the method of solving linear equations above. Explain
the steps in your computation. You may find it useful to collect
inspiration from the video in Example
3.30
.
3.6 The transposed matrix
Let be an matrix and an matrix. Then
By definition . This entry is given
by row-column multiplication of the -th row in and
the -th column in , which is the row-column multiplication of the
-th row in and the -th column in .
Let be a quadratic matrix. Prove that is invertible if and only if
is invertible.
In the sage window below, you are supposed to experiment a
bit by entering an arbitrary matrix and studying the quadratic
matrix . Is there anything special about this product? Press
the Further explanation button below the sage window to display
the rest of the exercise after(!) you have completed your
experimentation.
Further explanation
A quadratic matrix is called symmetric if . Prove that
is a symmetric matrix, where is an arbitrary matrix.
3.7 Symmetric matrices
Show that
is a symmetric matrix, when is a symmetric matrix and
is an arbitrary matrix. Both matrices are assumed
quadratic of the same dimensions.
You are also encouraged to watch the short video below
for an example with concrete numbers.
3.7.1 Positive definite matrices
Give examples of (non-zero) and matrices that are
positive definite and ones that fail to be positive
definite.
When is a diagonal matrix positive definite?
Let be a symmetric matrix. Show that
is not positive definite if .
3.7.2 Positive semi-definite matrices
for every .
Give an example of a non-zero matrix that is positive semi-definite,
but not positive definite.
When is a diagonal matrix positive semi-definite?
3.7.3 Symmetric reductions
Let be a symmetric matrix and an
invertible matrix. Then is
positive (semi) definite if and only if
is positive (semi) definite.
Every vector is equal to for a unique ,
since is invertible. Why? The upshot is that the equation
can be solved by multiplying both sides by giving
So we get
This computation shows that is positive (semi) definite if
is positive semi-definite. The same
reasoning with shows that is
positive (semi) definite if is positive (semi) definite.
Notice that it is important that only happens
when .
Let
be a diagonal matrix. What conditions must the diagonal
entries and satisfy in order for
to be positive definite?
Let
denote a symmetric matrix, where . Let
Show that is invertible and compute
Use this to show that is positive definite if and only if
and .
Let be the function defined by
Show that for every .