mscroggs.co.uk
mscroggs.co.uk

subscribe

Blog

 2020-02-06 
This is the third post in a series of posts about matrix methods.
Yet again, we want to solve \(\mathbf{A}\mathbf{x}=\mathbf{b}\), where \(\mathbf{A}\) is a (known) matrix, \(\mathbf{b}\) is a (known) vector, and \(\mathbf{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:
  1. Find the determinants of smaller blocks of the matrix to find the "matrix of minors".
  2. Multiply some of the entries by -1 to get the "matrix of cofactors".
  3. Transpose the matrix.
  4. 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{pmatrix} 1&-2&4\\ -2&3&-2\\ -2&2&2 \end{pmatrix}.$$
The result of the four steps above is the calculation
$$\frac1{\det\begin{pmatrix} 1&-2&4\\ -2&3&-2\\ -2&2&2 \end{pmatrix} }\begin{pmatrix} \det\begin{pmatrix}3&-2\\2&2\end{pmatrix}& -\det\begin{pmatrix}-2&4\\2&2\end{pmatrix}& \det\begin{pmatrix}-2&4\\3&-2\end{pmatrix}\\ -\det\begin{pmatrix}-2&-2\\-2&2\end{pmatrix}& \det\begin{pmatrix}1&4\\-2&2\end{pmatrix}& -\det\begin{pmatrix}1&4\\-2&-2\end{pmatrix}\\ \det\begin{pmatrix}-2&3\\-2&2\end{pmatrix}& -\det\begin{pmatrix}1&-2\\-2&2\end{pmatrix}& \det\begin{pmatrix}1&-2\\-2&3\end{pmatrix} \end{pmatrix}.$$
Calculating the determinants gives $$\frac12 \begin{pmatrix} 10&12&-8\\ 8&10&-6\\ 2&2&-1 \end{pmatrix},$$ which simplifies to
$$ \begin{pmatrix} 5&6&-4\\ 4&5&-3\\ 1&1&-\tfrac12 \end{pmatrix}.$$

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:
  1. Finding the determinant of \(n^2\) different \((n-1)\times(n-1)\) matrices.
  2. Multiplying \(\left\lfloor\tfrac{n}2\right\rfloor\) of these matrices by -1.
  3. Calculating the determinant of a \(n\times n\) matrix.
  4. Dividing \(n^2\) numbers by this determinant.
If \(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^2d_{n-1} + \left\lfloor\tfrac{n}2\right\rfloor + 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 \(\mathcal{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 \(\mathcal{O}(n^{2.373})\). For large \(n\), this is significantly smaller than \(\mathcal{O}(n!)\).

How many operations

Even if the quick \(\mathcal{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} + \left\lfloor\tfrac{n}2\right\rfloor + n^{2.373} + n^2.$$
This is \(\mathcal{O}(n^{4.373})\), and so for large matrices this will be slower than Gaussian elimination, which was \(\mathcal{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 \(\mathcal{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.

Similar posts

Gaussian elimination
Matrix multiplication
Happy √3-ϕ+3 Approximation Day!
A surprising fact about quadrilaterals

Comments

Comments in green were written by me. Comments in blue were not written by me.
 Add a Comment 


I will only use your email address to reply to your comment (if a reply is needed).

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "q" then "u" then "o" then "t" then "i" then "e" then "n" then "t" in the box below (case sensitive):

Archive

Show me a random blog post
 2020 

Jul 2020

Happy √3-ϕ+3 Approximation Day!

May 2020

A surprising fact about quadrilaterals
Interesting tautologies

Mar 2020

Log-scaled axes

Feb 2020

PhD thesis, chapter ∞
PhD thesis, chapter 5
PhD thesis, chapter 4
PhD thesis, chapter 3
Inverting a matrix
PhD thesis, chapter 2

Jan 2020

PhD thesis, chapter 1
Gaussian elimination
Matrix multiplication
Christmas (2019) is over
 2019 
▼ show ▼
 2018 
▼ show ▼
 2017 
▼ show ▼
 2016 
▼ show ▼
 2015 
▼ show ▼
 2014 
▼ show ▼
 2013 
▼ show ▼
 2012 
▼ show ▼

Tags

pi probability video games mathslogicbot tennis dragon curves cambridge hannah fry mathsjam plastic ratio games geometry rugby folding paper go convergence computational complexity realhats football european cup cross stitch palindromes craft pi approximation day misleading statistics braiding python inverse matrices christmas card game of life pac-man pythagoras data visualisation countdown numerical analysis a gamut of games propositional calculus chalkdust magazine chebyshev frobel geogebra latex reuleaux polygons determinants royal institution flexagons sound php light puzzles inline code dataset speed folding tube maps advent calendar statistics fractals arithmetic radio 4 trigonometry hats triangles sobolev spaces sport machine learning error bars twitter talking maths in public ternary books curvature simultaneous equations bubble bobble weather station approximation matrices matrix of minors coins manchester science festival news quadrilaterals ucl polynomials data pizza cutting accuracy the aperiodical golden spiral reddit rhombicuboctahedron binary game show probability stickers final fantasy gaussian elimination world cup programming noughts and crosses boundary element methods manchester royal baby draughts matrix of cofactors electromagnetic field london underground bodmas asteroids big internet math-off logic hexapawn preconditioning harriss spiral finite element method people maths sorting graph theory oeis london squares martin gardner map projections raspberry pi matt parker platonic solids gerry anderson menace mathsteroids wool graphs logs chess golden ratio signorini conditions dates nine men's morris exponential growth national lottery tmip phd javascript estimation interpolation christmas bempp wave scattering matrix multiplication captain scarlet weak imposition

Archive

Show me a random blog post
▼ show ▼
© Matthew Scroggs 2012–2020