Linear Algebra is the algebra of “lines”. It’s used to create computer graphics.

Vectors

To Computer Scientists a vector is a container where order matters and repititions are allowed. A 2d vector is considered 2 dimensional because it has 2 items in it. Example of a 2d vector: <5, 6>.

To a physicist, a vector has magnitude and direction. To a physitict you can move a vector all around the plane and it’ll remain the same vector.

img

So what is it? Well, it’s both. A vector is both a container of numbers and a representation of magnitude and direction. In this article we’ll focus on the computer science perspective.

An N-vector has n components (elements), each component called

The number of components a vector has is the number of dimensions a vector has.

Two vectors can be added like so:

You can only add two vectors if the vectors have the same number of components.

Scalar multiplcation is where you increase every item in a vector by R. Let R be a real number then:

The length of a vector a, |a|, can be calculated with Pythagoras’ formula

Some important facts:

A vector space is a list, V, of n-vectors where each vector is defined strictly using a type of number (real, rational etc) and if and only if:

Given any number, R, from the original space (real numbers, integers, etc) and then

The superscript number ontop of a set of numbers such as is the set of all real valued (numbers that are in the real numbers) n-vectors where each component is in the set of Real numbers.

2-vectors have 2 dimensions, X and Y: <X, Y>. 3-vectors have <X, Y, Z>. img

A matrix is a container which can have many dimensions. Paul said that this won’t be on the first class test but he might ask you to multiply matrices out.

We can represent a shape by representing its “corners” in a vector like so:

So most shapes are just corners with them filed in.

Take this square for instance:

img

If you know the corners of this square, you just draw the corners, connect them to one another and colour it in. Almost all shapes have this property (not circles, since circles do not have corners).

If we wanted to scale this shape by a factor of s, we can use this matrix:

To “scale a shape” means to increase / decrease the size of the shape. If we increase how far away the corners are away from eachother then we increse the size of the shape.

So you have a vector, which can be represented as a matrix. Just to drive the point home:

This is just one corner, we obviously scale every corner by the scalar but we start with one corner and work our way through all the corners.

This is how you scale a 3-dimensional object.

The matrix applied to scale the vector is an example of a linear transformation.

An operation, T, is a *linear transformation* if:

  1. For any pair of vectors, v and u, belonging to the vector space, V: T(v + u) = T(v) + T(u)
  2. For every vector in V and any r (real number) in the set used by R (natural numbers, real, rational): T(rv) = rT(v)

What if we wanted to move a point, say <1, 2> to <5, 6>?

Well, this is easy!

The difference between 1 and 5 is 4, so that’s why the 4 is there.

We can generalise this like so:

Say you want to move a point <x, y> to the point <x + p, y + q>

What if we wanted to rotate a a point anticlockwise about <0, 0> by theta to <q, s>?

img

Advance Matrices

An n x n matrix has n rows and n columns. The value in row i and column j of the matrix is denoted as:

The number of rows and columns do not have to be equal, but in most cases they are.

Directed Graphs represent in Matrices

We can represent directed graphs using matrices.

The following graph can be represented by the 5 x 5 matrix:

img

Where the rows are nodes 1 to 5 and so are the columns. If node 1 is connected to node 2, row 1 column 2 is set to 1. If node 2 is not connect to node 1, row 2 column 1 is set to 0.

Operations on n x m matrices

2 matrices, N rows and M columns.

We have 2 matrices, A and B. We want to add them like so:

We can add them like so:

So we just add the corresponding element in each matrix.

We can’t mix dimensions with addition of matrices.

We can scale a matrix by a real number, R, like so:

Transposition of matrix

Suppose we have a matrix called A. The transposition is formed by “swapping the rows and columns” The entries in the first row become the entries in the first column, the entries in the second row become the entries in the second column aod so on.

Multiplying Matrices

The matrix A with n rows and m colums and our second matrix B with m rows and r columns.

When we multiply them together the resulting matrix, C, will have n rows and r columns. The number of rows in the first matrix has to be the same as the number of columns in our second matrix.

So we just multiply all of the entries in the ith row by all of the entries in the jth column in the two matrices.

Symetric Matrices

With two matrices they are said to be symetric when:

When the item in the ith row and jth column is equal to the item in the jth row and ith column for every item in the matrices they are said to be equal.

Identity Matrix

The n x n Identity matrix uses only the values 0 and 1.

If the values in the ith row and jth column are equal, that data point is a 1. If they are not equal, the data point is a 0.

Take any n x n matrix, A.

Then the identity matrix, I, satisfies:

Multiplying any matrix by the identity matrix results in the original matrix.

The identity matrix is this super cool matrix that has the number “1” diagonally across it.

If we have a 2 x 2 matrix, A, then the identity matrix is:

And then a 3 x 3 matrix’s identity matrix looks like:

And so on. As long as you have 1’s on this diagonal line and everything else is a 0 then it’s an identity matrix.

Let’s multiply the identity matrix by a general matrix to see how the above law obeys it.

So any matrix multiplied by it’s identity matrix is just the matrix itself.

Inverse of a Matrix

We want to find a matrix which is the inverse of A given by the symbol:

Which has the property

Where if you multiply the inverse of a matrix by the matrix you will find the identity matrix.

This is actually how division works with matrices. Well, it’s the equivalent of division.

Not all matrices have an inverse. The singular number 0 has no inverse.

When a matrix does not have an inverse it is referred to singular.

Such calculations such as finding the inverse of a 4x4 matrix or larger values of n you really don’t want to do that by hand so it’s best left to an already programmed solution.

The Determinant of a Matrix

There is a basic but rather tedious procedure that can be applied to decide if A (matrix) is invertible.

Suppose we take any n x n matrix A and we choose any row and any column of that matrix then we can form another matrix defined by row i and column j such as:

is the matrix A, turning it into an (n-1) x (n-1) matrix by deleting its ith row and the jth column.

In other terms, we delete the ith row and the jth column. We’re deleting a column and a row from a matrix to produce a new matrix.

To calculate the determinant we can use a recursive algorithm.

  1. If n = 2 (A is a 2 x 2 matrix):

  2. if n > 2:

Let’s calculate the determinant of the following matrix:

So because it is not a 2 x 2 matrix we have to form sub matrices by deleting the first row and then the first column, then the first row and second column, then the first row and third column to form these matrices:

You’ll notice that the notation:

is used here to define what rows are missing. In this case, if you take off the first row and first column of the original matrix you get left with .

To find the determinant of a 2x2 matrix, we multiply the items along the main diagonal and subtract the entries by the opposite diagonal.

Do you see how it’s diagnonal?

If we do the same to the other matrices we get:

Now we have to combine the three determinant values together in a particular way to construct the determinant for the matrix overall.

So you time’s by -1 (I’m not sure why) but you put -1 to the power of the row and columns missing in the matrix. So for the first sub matrix we have this notation:

Which is why we do it to the power of (1+1). Paul doesn’t actually explain this, nor does he explain why we want -1. I assume it’s just part of the algorithm.

We then times this by the first item in the 1st row and 1st column in the original matrix, which is 0, and then we multiplky that by the determinant of the matrix formed by deleting the first row and first column (first sub matrix)

So in total we have:

Now we do something similar for the second matrix:

So that’s sub matrix

And 1 + 2 is 3, so to the power of 3. Then we multiply it by the item in the original matrix which is in the first row, second column which is 5.

Times that by the determinant of the second mini matrix.

The next one works the same.

Now we just do the maths:

I can only guess that we times by -1 because the determinant involves the inverse of a matrix and to find the inverse of a real number that isn’t 0 you times by -1, so I’m under the assumption that if we times a matrix by -1 we get the inverse of that matrix.

The determinant of the matrix is 242.

If the determinant of A is not equal to 0 then an inverse of the matrix exists (it is not singular).

Adjoint of a Matrix

We have an n x n matrix A, then we look at the ith row and jth column of that matrix and for each value of that matrix add the determinant formed by deleting ith row and jth column then the adjoint of any matrix is the n x n matrix whose individal lengths are given in the following way:

This formula finds the inverse of a matrix.

We need the determinants of the matrix and the determinant of the three sub matrices, calculated earlier.

We work out the determinant of every possible sub matrix:

When we multiply a matrix by its inverse matrix we get the identity matrix.

Paul explicitly said that this won’t come up in the test. Lecture 19 13th march 2018 at 9am minute 37 second 14 he says “considering this took us 2 lectures to cover and you have an estimated 5 minutes without a calculator in the exam, do you think this will appear on the exam?”.

At minute 38 second 1 he says “there is absolutely no point in asking questions like this, so this won’t come up.” At minute 38 and second 39 he says “in the real world we use algorithms in programming languages already coded for us. We do not need to calculate by hand.”

Charecteristic Matrices

Suppose we have a real valued n x n matrix, A. Suppose further we want to find all the n-vectors, X, that have the following properties with respect to A:

  1. X != 0. X has no zero component.
  2. There is a value, λ , for which Ax^t = λx^t

How do we go about finding X and λ?

Let’s use a trick to calculate this.

We’ll rewrite the relationship

as:

and we can simplfy this equation into:

TK work out identity matrix TK identity matrix?