Blog

Showing posts tagged "matrices". Show all posts.

Inverting a matrix

2020-02-06

This is the third post in a series of posts about matrix methods.

Previous post in series ~ View all posts in series

Yet again, we want to solve

A x = b

, where

A

is a (known) matrix,

b

is a (known) vector, and

x

is an unknown vector.

In the previous post in this series, we used Gaussian elimination to invert a matrix. You may, however, have been taught an alternative method for calculating the inverse of a matrix. This method has four steps:

Find the determinants of smaller blocks of the matrix to find the "matrix of minors".
Multiply some of the entries by -1 to get the "matrix of cofactors".
Transpose the matrix.
Divide by the determinant of the matrix you started with.

An example

As an example, we will find the inverse of the following matrix.

(\begin{matrix} 1 & - 2 & 4 \\ - 2 & 3 & - 2 \\ - 2 & 2 & 2 \end{matrix}) .

The result of the four steps above is the calculation

\frac{1}{det (\begin{matrix} 1 & - 2 & 4 \\ - 2 & 3 & - 2 \\ - 2 & 2 & 2 \end{matrix})} (\begin{matrix} det (\begin{matrix} 3 & - 2 \\ 2 & 2 \end{matrix}) & - det (\begin{matrix} - 2 & 4 \\ 2 & 2 \end{matrix}) & det (\begin{matrix} - 2 & 4 \\ 3 & - 2 \end{matrix}) \\ - det (\begin{matrix} - 2 & - 2 \\ - 2 & 2 \end{matrix}) & det (\begin{matrix} 1 & 4 \\ - 2 & 2 \end{matrix}) & - det (\begin{matrix} 1 & 4 \\ - 2 & - 2 \end{matrix}) \\ det (\begin{matrix} - 2 & 3 \\ - 2 & 2 \end{matrix}) & - det (\begin{matrix} 1 & - 2 \\ - 2 & 2 \end{matrix}) & det (\begin{matrix} 1 & - 2 \\ - 2 & 3 \end{matrix}) \end{matrix}) .

Calculating the determinants gives

\frac{1}{2} (\begin{matrix} 10 & 12 & - 8 \\ 8 & 10 & - 6 \\ 2 & 2 & - 1 \end{matrix}),

which simplifies to

(\begin{matrix} 5 & 6 & - 4 \\ 4 & 5 & - 3 \\ 1 & 1 & - \frac{1}{2} \end{matrix}) .

How many operations

This method can be used to find the inverse of a matrix of any size. Using this method on an

n \times n

matrix will require:

Finding the determinant of $n^{2}$ different $(n - 1) \times (n - 1)$ matrices.
Multiplying $⌊ \frac{n}{2} ⌋$ of these matrices by -1.
Calculating the determinant of a $n \times n$ matrix.
Dividing $n^{2}$ numbers by this determinant.

d_{n}

is the number of operations needed to find the determinant of an

n \times n

matrix, the total number of operations for this method is

n^{2} d_{n - 1} + ⌊ \frac{n}{2} ⌋ + d_{n} + n^{2} .

How many operations to find a determinant

If you work through the usual method of calculating the determinant by calculating determinants of smaller blocks the combining them, you can work out that the number of operations needed to calculate a determinant in this way is

O (n!)

. For large values of

n

, this is significantly larger than any power of

n

There are other methods of calculating determinants: the fastest of these is

O (n^{2.373})

. For large

n

, this is significantly smaller than

O (n!)

How many operations

Even if the quick

O (n^{2.373})

method for calculating determinants is used, the number of operations required to invert a matrix will be of the order of

n^{2} (n - 1)^{2.373} + ⌊ \frac{n}{2} ⌋ + n^{2.373} + n^{2} .

This is

O (n^{4.373})

, and so for large matrices this will be slower than Gaussian elimination, which was

O (n^{3})

In fact, this method could only be faster than Gaussian elimination if you discovered a method of finding a determinant faster than

O (n)

. This seems highly unlikely to be possible, as an

n \times n

matrix has

n^{2}

entries and we should expect to operate on each of these at least once.

So, for large matrices, Gaussian elimination looks like it will always be faster, so you can safely forget this four-step method.

Previous post in series

Gaussian elimination

This is the third post in a series of posts about matrix methods.

View all posts in series

Tags: matrices, inverse matrices, gaussian elimination, computational complexity, determinants, matrix of minors, matrix of cofactors

×3

×2

(Click on one of these icons to react to this blog post)

You might also enjoy...

Gaussian elimination

MENACE

Christmas (2023) is over

Christmas card 2023

Comments

Comments in green were written by me. Comments in blue were not written by me.

Add a Comment

Gaussian elimination

2020-01-24

This is the second post in a series of posts about matrix methods.

Previous post in series ~ View all posts in series ~ Next post in series

We want to solve

A x = b

, where

A

is a (known) matrix,

b

is a (known) vector, and

x

is an unknown vector.

This matrix system can be thought of as a way of representing simultaneous equations. For example, the following matrix problem and system of simultaneous equations are equivalent.

\begin{aligned} (\begin{array}{c} 2 & 1 \\ 3 & 1 \end{array}) x & = (\begin{array}{c} 3 \\ 4 \end{array}) & \begin{array}{r} 2 x + 2 y = 3 \\ 3 x + 2 y = 4 \end{array} \end{aligned}

The simultaneous equations here would usually be solved by adding or subtracting the equations together. In this example, subtracting the first equation from the second gives

x = 1

. From there, it is not hard to find that

y = \frac{1}{2}

One approach to solving

A x = b

is to find the inverse matrix

A^{- 1}

, and use

x = A^{- 1} b

. In this post, we use Gaussian elimination—a method that closely resembles the simultaneous equation method—to find

A^{- 1}

Gaussian elimination

As an example, we will use Gaussian elimination to find the inverse of the matrix

(\begin{matrix} 1 & - 2 & 4 \\ - 2 & 3 & - 2 \\ - 2 & 2 & 2 \end{matrix}) .

First, write the matrix with an identity matrix next to it.

(\begin{array}{cccccc} 1 & - 2 & 4 & 1 & 0 & 0 \\ - 2 & 3 & - 2 & 0 & 1 & 0 \\ - 2 & 2 & 2 & 0 & 0 & 1 \end{array})

Our aim is then to use row operations to change the matrix on the left of the vertical line into the identity matrix, as the matrix on the right will then be the inverse. We are allowed to use two row operations: we can multiply a row by a scalar; or we can add a multiple of a row to another row. These operations closely resemble the steps used to solve simultaneous equations.

We will get the matrix to the left of the vertical line to be the identity in a systematic manner: our first aim is to get the first column to read 1, 0, 0. We already have the 1; to get the 0s, add 2 times the first row to both the second and third rows.

(\begin{array}{cccccc} 1 & - 2 & 4 & 1 & 0 & 0 \\ 0 & - 1 & 6 & 2 & 1 & 0 \\ 0 & - 2 & 10 & 2 & 0 & 1 \end{array})

Our next aim is to get the second column to read 0, 1, 0. To get the 1, we multiply the second row by -1.

(\begin{array}{cccccc} 1 & - 2 & 4 & 1 & 0 & 0 \\ 0 & 1 & - 6 & - 2 & - 1 & 0 \\ 0 & - 2 & 10 & 2 & 0 & 1 \end{array})

To get the 0s, we add 2 times the second row to both the first and third rows.

(\begin{array}{cccccc} 1 & 0 & - 8 & - 3 & - 2 & 0 \\ 0 & 1 & - 6 & - 2 & - 1 & 0 \\ 0 & 0 & - 2 & - 2 & - 2 & 1 \end{array})

Our final aim is to get the third column to read 0, 0, 1. To get the 1, we multiply the third row by -½.

(\begin{array}{cccccc} 1 & 0 & - 8 & - 3 & - 2 & 0 \\ 0 & 1 & - 6 & - 2 & - 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & - \frac{1}{2} \end{array})

To get the 0s, we add 8 and 6 times the third row to the first and second rows (respectively).

(\begin{array}{cccccc} 1 & 0 & 0 & 5 & 6 & - 4 \\ 0 & 1 & 0 & 4 & 5 & - 3 \\ 0 & 0 & 1 & 1 & 1 & - \frac{1}{2} \end{array})

We have the identity on the left of the vertical bar, so we can conclude that

{(\begin{matrix} 1 & - 2 & 4 \\ - 2 & 3 & - 2 \\ - 2 & 2 & 2 \end{matrix})}^{- 1} = (\begin{matrix} 5 & 6 & - 4 \\ 4 & 5 & - 3 \\ 1 & 1 & - \frac{1}{2} \end{matrix}) .

How many operations

This method can be used on matrices of any size. We can imagine doing this with an

n \times n

matrix and look at how many operations the method will require, as this will give us an idea of how long this method would take for very large matrices. Here, we count each use of

+

-

\times

and

\div

as a (floating point) operation (often called a flop).

Let's think about what needs to be done to get the

i

th column of the matrix equal to 0, ..., 0, 1, 0, ..., 0.

First, we need to divide everything in the

i

th row by the value in the

i

th row and

i

th column. The first

i - 1

entries in the column will already be 0s though, so there is no need to divide these. This leaves

n - (i - 1)

entries that need to be divided, so this step takes

n - (i - 1)

, or

n + 1 - i

operations.

Next, for each other row (let's call this the

j

th row), we add or subtract a multiple of the

i

th row from the

j

th row. (Again the first

i - 1

entries can be ignored as they are 0.) Multiplying the

i

th row takes

n + 1 - i

operations, then adding/subtracting takes another

n + 1 - i

operations. This needs to be done for

n - 1

rows, so takes a total of

2 (n - 1) (n + 1 - i)

operations.

After these two steps, we have finished with the

i

th column, in a total of

(2 n - 1) (n + 1 - i)

operations.

We have to do this for each

i

from 1 to

n

, so the total number of operations to complete Gaussian elimination is

(2 n - 1) (n + 1 - 1) + (2 n - 1) (n + 1 - 2) + . . . + (2 n - 1) (n + 1 - n)

This simplifies to

\frac{1}{2} n (2 n - 1) (n + 1)

n^{3} + \frac{1}{2} n^{2} - \frac{1}{2} n .

The highest power of

n

n^{3}

, so we say that this algorithm is an order

n^{3}

algorithm, often written

O (n^{3})

. We focus on the highest power of

n

as if

n

is very large,

n^{3}

will be by far the largest number in the expression, so gives us an idea of how fast/slow this algorithm will be for large matrices.

n^{3}

is not a bad start—it's far better than

n^{4}

n^{5}

, or

2^{n}

—but there are methods out there that will take less than

n^{3}

operations. We'll see some of these later in this series.

Previous post in series

Matrix multiplication

This is the second post in a series of posts about matrix methods.

View all posts in series

Next post in series

Inverting a matrix

Tags: matrices, inverse matrices, computational complexity, gaussian elimination

×1

(Click on one of these icons to react to this blog post)

You might also enjoy...

Inverting a matrix

MENACE

Christmas (2023) is over

Christmas card 2023

Comments

Comments in green were written by me. Comments in blue were not written by me.

Add a Comment

Matrix multiplication

2020-01-23

This is the first post in a series of posts about matrix methods.

View all posts in series ~ Next post in series

When you first learn about matrices, you learn that in order to multiply two matrices, you use this strange-looking method involving the rows of the left matrix and the columns of this right.

It doesn't immediately seem clear why this should be the way to multiply matrices. In this blog post, we look at why this is the definition of matrix multiplication.

Simultaneous equations

Matrices can be thought of as representing a system of simultaneous equations. For example, solving the matrix problem

[\begin{matrix} 2 & 5 & 2 \\ 1 & 0 & - 2 \\ 3 & 1 & 1 \end{matrix}] (\begin{matrix} x \\ y \\ z \end{matrix}) = (\begin{matrix} 14 \\ - 16 \\ - 4 \end{matrix})

is equivalent to solving the following simultaneous equations.

\begin{aligned} 2 x + 5 y + 2 z & = 14 \\ 1 x + 0 y - 2 z & = - 16 \\ 3 x + 1 y + 1 z & = - 4 \end{aligned}

Two matrices

Now, let

A

and

C

be two 3×3 matrices, let

b

by a vector with three elements, and let

x = (x, y, z)

. We consider the equation

A C x = b .

In order to understand what this equation means, we let

y = C x

and think about solving the two simuntaneous matrix equations,

\begin{aligned} A y & = b \\ C x & = y . \end{aligned}

We can write the entries of

A

C

x

y

and

b

\begin{aligned} A & = [\begin{array}{c} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{23} \end{array}] & C & = [\begin{array}{c} c_{11} & c_{12} & c_{13} \\ c_{21} & c_{22} & c_{23} \\ c_{31} & c_{32} & c_{23} \end{array}] \end{aligned}

\begin{aligned} x & = (\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \end{array}) & y & = (\begin{array}{c} y_{1} \\ y_{2} \\ y_{3} \end{array}) & b & = (\begin{array}{c} b_{1} \\ b_{2} \\ b_{3} \end{array}) \end{aligned}

We can then write out the simultaneous equations that

A y = b

and

C x = y

represent:

\begin{aligned} a_{11} y_{1} + a_{12} y_{2} + a_{13} y_{3} & = b_{1} & c_{11} x_{1} + c_{12} x_{2} + c_{13} x_{3} & = y_{1} \\ a_{21} y_{1} + a_{22} y_{2} + a_{23} y_{3} & = b_{2} & c_{21} x_{1} + c_{22} x_{2} + c_{23} x_{3} & = y_{2} \\ a_{31} y_{1} + a_{32} y_{2} + a_{33} y_{3} & = b_{3} & c_{31} x_{1} + c_{32} x_{2} + c_{33} x_{3} & = y_{3} \end{aligned}

Substituting the equations on the right into those on the left gives:

\begin{aligned} a_{11} (c_{11} x_{1} + c_{12} x_{2} + c_{13} x_{3}) + a_{12} (c_{21} x_{1} + c_{22} x_{2} + c_{23} x_{3}) + a_{13} (c_{31} x_{1} + c_{32} x_{2} + c_{33} x_{3}) & = b_{1} \\ a_{21} (c_{11} x_{1} + c_{12} x_{2} + c_{13} x_{3}) + a_{22} (c_{21} x_{1} + c_{22} x_{2} + c_{23} x_{3}) + a_{23} (c_{31} x_{1} + c_{32} x_{2} + c_{33} x_{3}) & = b_{2} \\ a_{31} (c_{11} x_{1} + c_{12} x_{2} + c_{13} x_{3}) + a_{32} (c_{21} x_{1} + c_{22} x_{2} + c_{23} x_{3}) + a_{33} (c_{31} x_{1} + c_{32} x_{2} + c_{33} x_{3}) & = b_{3} \end{aligned}

Gathering the terms containing

x_{1}

x_{2}

and

x_{3}

leads to:

\begin{aligned} (a_{11} c_{11} + a_{12} c_{21} + a_{13} c_{31}) x_{1} + (a_{11} c_{12} + a_{12} c_{22} + a_{13} c_{32}) x_{2} + (a_{11} c_{13} + a_{12} c_{23} + a_{13} c_{33}) x_{3} & = b_{1} \\ (a_{21} c_{11} + a_{22} c_{21} + a_{23} c_{31}) x_{1} + (a_{21} c_{12} + a_{22} c_{22} + a_{23} c_{32}) x_{2} + (a_{21} c_{13} + a_{22} c_{23} + a_{23} c_{33}) x_{3} & = b_{2} \\ (a_{31} c_{11} + a_{32} c_{21} + a_{33} c_{31}) x_{1} + (a_{31} c_{12} + a_{32} c_{22} + a_{33} c_{32}) x_{2} + (a_{31} c_{13} + a_{32} c_{23} + a_{33} c_{33}) x_{3} & = b_{3} \end{aligned}

We can write this as a matrix:

[\begin{matrix} a_{11} c_{11} + a_{12} c_{21} + a_{13} c_{31} & a_{11} c_{12} + a_{12} c_{22} + a_{13} c_{32} & a_{11} c_{13} + a_{12} c_{23} + a_{13} c_{33} \\ a_{21} c_{11} + a_{22} c_{21} + a_{23} c_{31} & a_{21} c_{12} + a_{22} c_{22} + a_{23} c_{32} & a_{21} c_{13} + a_{22} c_{23} + a_{23} c_{33} \\ a_{31} c_{11} + a_{32} c_{21} + a_{33} c_{31} & a_{31} c_{12} + a_{32} c_{22} + a_{33} c_{32} & a_{31} c_{13} + a_{32} c_{23} + a_{33} c_{33} \end{matrix}] x = b

This equation is equivalent to

A C x = b

, so the matrix above is equal to

A C

. But this matrix is what you get if follow the row-and-column matrix multiplication method, and so we can see why this definition makes sense.

This is the first post in a series of posts about matrix methods.

View all posts in series

Next post in series

Gaussian elimination

Tags: matrices, matrix multiplication, simultaneous equations

(Click on one of these icons to react to this blog post)

You might also enjoy...

MENACE

Christmas (2023) is over

Christmas card 2023

Blog

Inverting a matrix

An example

How many operations

How many operations to find a determinant

How many operations

You might also enjoy...

Comments

Gaussian elimination

Gaussian elimination

How many operations

You might also enjoy...

Comments

Matrix multiplication

Simultaneous equations

Two matrices

You might also enjoy...

Comments

Archive

Mar 2025

Jan 2025

Dec 2024

Nov 2024

Feb 2024

Jan 2024

Dec 2023

Nov 2023

Sep 2023

May 2023

Apr 2023

Mar 2023

Feb 2023

Jan 2023

Dec 2022

Nov 2022

Oct 2022

Mar 2022

Feb 2022

Jan 2022

Dec 2021

Nov 2021

Sep 2021

May 2021

Jan 2021

Dec 2020

Nov 2020

Jul 2020

May 2020

Mar 2020

Feb 2020

Jan 2020

Dec 2019

Nov 2019

Sep 2019

Jul 2019

Jun 2019

Apr 2019

Mar 2019

Jan 2019

Dec 2018

Nov 2018

Sep 2018

Jul 2018

Jun 2018

May 2018

Apr 2018

Mar 2018

Jan 2018

Dec 2017

Nov 2017

Jun 2017

Mar 2017

Feb 2017

Jan 2017

Dec 2016

Nov 2016

Oct 2016

Sep 2016

Jul 2016

Jun 2016