MathLogic

📘 Complexity Theory — Post 9: Complexity of Matrix Inversion

In the previous post, we saw that the determinant of an n by n matrix can be computed efficiently using elimination in O(n³) time.

Now let us look at another important matrix operation:

Finding the inverse of a matrix.

Suppose A is an invertible n by n matrix.

We want to find A⁻¹ such that:

A × A⁻¹ = I

where I is the identity matrix.

A standard way to compute the inverse is to use Gaussian elimination.

We start with the augmented matrix:

[A | I]

Then we perform row operations until the left side becomes the identity matrix:

[I | A⁻¹]

So matrix inversion is essentially built from the same elimination process we studied before.

The main computational work comes from Gaussian elimination.

For a dense n by n matrix, this requires roughly:

O(n³)

operations.

Therefore:

Matrix inversion → O(n³)

Why cubic?

A useful way to think about it is:

There are about n elimination stages.

At each stage, we update roughly n² entries.

So the total work behaves like:

n × n² = n³

which gives:

O(n³)

There is also another way to understand the inverse.

The columns of A⁻¹ can be found by solving n different linear systems:

A x₁ = e₁

A x₂ = e₂
..

A xₙ = eₙ

where e₁, e₂, ..., eₙ are the standard basis vectors.

If we solved each system completely from scratch, that would be unnecessarily expensive.

Instead, we can factor or eliminate the matrix once and reuse the result for all right-hand sides.

That keeps the total cost at about O(n³).

This gives us another important lesson:

Good algorithms often reuse previous computations instead of repeating the same expensive work.

We can now compare:

Matrix addition → O(n²)

Matrix-vector multiplication → O(n²)

Matrix multiplication → O(n³)

Gaussian elimination → O(n³)

Determinant by elimination → O(n³)

Matrix inversion → O(n³)

One practical note:

In numerical computation, if we only want to solve

A x = b,

we usually do not explicitly compute A⁻¹ first.

It is generally better to solve the linear system directly.

Main takeaway:

Matrix inversion is another classical example of cubic-time computation for dense matrices.

In the next post, we can move away from matrices for a moment and study **searching algorithms**:

Linear search versus binary search.

That will introduce an important new complexity:

O(log n)

📘 Complexity Theory — Post 8: Complexity of Computing a Determinant

In the previous post, we saw that Gaussian elimination solves a dense n by n linear system in O(n³) time.

Now let us study another familiar matrix operation:

Computing the determinant of an n by n matrix.

The interesting part is that the complexity depends strongly on the method we choose.

🔹 Method 1: Expansion by minors

For a small matrix, we often compute the determinant by expanding along a row or column.

For example, for a 3 by 3 matrix, we reduce the problem to determinants of smaller 2 by 2 matrices.

For a 4 by 4 matrix, we reduce it to several 3 by 3 determinants.

Then each of those produces several 2 by 2 determinants.

This creates a branching computation.

Roughly, the work grows like:

n!

This is factorial growth.

Factorial growth becomes extremely large very quickly.

For example:

5! = 120

10! = 3,628,800

20! is already enormous.

So determinant expansion by minors is not practical for large matrices.

---

🔹 Method 2: Gaussian elimination

There is a much better approach.

We can use row operations to transform the matrix into an upper triangular matrix.

For a triangular matrix, the determinant is simply the product of the diagonal entries.

The elimination step costs about:

O(n³)

and multiplying the n diagonal entries costs only:

O(n)

So the total complexity is dominated by:

O(n³)

Therefore:

Determinant by elimination → O(n³)

---

This gives us a very important lesson.

The mathematical problem is the same:

Compute det(A)

But the algorithm changes the complexity dramatically.

Expansion by minors → roughly factorial growth

Gaussian elimination → O(n³)

So when analyzing complexity, we should not ask only:

"What is the complexity of computing the determinant?"

A better question is:

"What is the complexity of this algorithm for computing the determinant?"

This distinction is fundamental in complexity theory.

The same problem may have:

a slow algorithm,

a faster algorithm,

and sometimes an algorithm whose best possible complexity is still unknown.

Main takeaway:

Complexity belongs to an algorithm, not just to a mathematical formula.

In the next post, we can study **matrix inversion** and see why its standard complexity is also closely related to O(n³).

📘 Complexity Theory — Post 7: Complexity of Gaussian Elimination

So far, we have seen:

Vector operations → O(n)

Matrix addition → O(n²)

Matrix-vector multiplication → O(n²)

Matrix multiplication → O(n³)

Now let us study another fundamental operation in linear algebra:

Solving a system of linear equations.

Suppose we have n equations in n unknowns.

A standard method for solving such a system is Gaussian elimination.

The main idea is simple:

We use one row to eliminate one variable from the rows below it.

Then we move to the next row and repeat.

For example, with three variables, we may start with:

a11 x1 + a12 x2 + a13 x3 = b1

a21 x1 + a22 x2 + a23 x3 = b2

a31 x1 + a32 x2 + a33 x3 = b3

First, we use the first equation to eliminate x1 from the equations below it.

Then we use the second equation to eliminate x2 from the last equation.

Eventually, the system becomes triangular.

After that, we solve the variables by back substitution.

The interesting question is:

How much work does this require for an n by n system?

At the first elimination step, we work with almost the whole matrix.

At the next step, the remaining active part is slightly smaller.

Then smaller again.

Roughly, the amount of work behaves like:

n² + (n−1)² + (n−2)² + ... + 1²

This sum grows proportionally to n³.

Therefore, the elimination phase has complexity:

O(n³)

Back substitution is cheaper.

It requires roughly O(n²) work.

So the total complexity is dominated by the elimination phase.

Therefore:

Gaussian elimination → O(n³)

This gives us an important complexity principle:

When an algorithm has several stages, the stage with the fastest growth usually determines the overall complexity.

For example:

Elimination → O(n³)

Back substitution → O(n²)

Total → O(n³)

because the cubic term dominates the quadratic term for large n.

Another way to understand this is:

At each of about n stages, we may update roughly n² matrix entries.

So approximately:

n stages × n² work per stage = n³ work

Hence:

O(n³)

This is why solving large dense linear systems becomes expensive very quickly.

If n doubles, cubic work becomes about:

2³ = 8

times larger.

So a problem twice as large may require roughly eight times as much work.

The main takeaway is:

Gaussian elimination is a natural example of cubic complexity.

In the next post, we can look at the complexity of the determinant and see why different algorithms for the same mathematical quantity can have very different costs.

📘 Complexity Theory — Post 6: Complexity of Matrix Multiplication

In the previous post, we studied matrix-vector multiplication and saw that multiplying an n by n matrix by a vector of length n requires O(n²) work.

Now let us move one step further:

Multiplying two n by n matrices.

Suppose we have two matrices:

A and B

and we want to compute:

C = AB

The result C is also an n by n matrix.

The key idea is this:

Each entry of C is obtained by taking one row of A and one column of B and computing their dot product.

For example, the entry in row 1 and column 1 is obtained from:

row 1 of A · column 1 of B

That dot product requires about n multiplications and n additions.

So computing one entry of C costs:

O(n)

But how many entries does C have?

Since C is an n by n matrix, it has:

n² entries

Therefore, we compute n² dot products.

Each dot product costs O(n).

So the total complexity is:

n² × O(n)

which gives:

O(n³)

This is the complexity of the standard matrix multiplication algorithm.

Let us see it another way.

There are:

n choices of row from A

n choices of column from B

and for each row-column pair, we perform a dot product of length n.

So the total work is proportional to:

n × n × n

which gives:

n³

Therefore:

Standard matrix multiplication → O(n³)

A small example makes this easier to see.

For two 2 by 2 matrices:

The result has 4 entries.

Each entry requires a dot product of length 2.

So we need about:

4 × 2 = 8 multiplications.

For two 3 by 3 matrices:

The result has 9 entries.

Each entry requires 3 multiplications.

So we need about:

9 × 3 = 27 multiplications.

For two n by n matrices:

n² output entries × n multiplications per entry = n³ multiplications.

This also explains why matrix multiplication is more expensive than matrix-vector multiplication.

Matrix-vector multiplication:

n output entries

Each costs O(n)

Total: O(n²)

Matrix-matrix multiplication:

n² output entries

Each costs O(n)

Total: O(n³)

This is an important pattern in complexity analysis:

Count how many outputs we must compute, then ask how much work is needed for each output.

One important note:

O(n³) is the complexity of the standard or classical matrix multiplication algorithm.

More advanced algorithms can multiply matrices faster than O(n³), but we will discuss that later.

For now, the important idea is:

One output entry = one dot product = O(n)

n² output entries = O(n³)

In the next post, we can study another fundamental linear algebra operation:

Solving a system of linear equations using Gaussian elimination.

This will show us another important example of O(n³) complexity.

📘 Complexity Theory — Post 5: Complexity of Matrix-Vector Multiplication

In the previous post, we saw that adding two n by n matrices requires n² additions, so matrix addition has complexity O(n²).

Now let us look at a more interesting operation:

Multiplying an n by n matrix by a vector of length n.

Suppose

A is an n by n matrix

and

x is a vector of length n.

The result is another vector:

y = Ax

How is each entry of y computed?

Each output entry is the dot product of one row of the matrix with the vector x.

For example, the first output entry is obtained from:

first row of A · x

The second output entry is obtained from:

second row of A · x

and so on.

Now recall from Post 3 that one dot product of two vectors of length n requires:

n multiplications

and approximately

n - 1 additions.

So one row requires O(n) work.

But the matrix has n rows.

Therefore, we perform this dot-product calculation n times.

So the total work is roughly:

n × n

which gives:

n²

Therefore, standard matrix-vector multiplication has complexity:

O(n²)

Another way to see this is to count the operations directly.

For an n by n matrix:

there are n output entries,

and each output entry requires about n multiplications and n additions.

So the total number of elementary operations grows proportionally to n².

For example:

A 2 by 2 matrix times a vector requires about 4 multiplications.

A 10 by 10 matrix times a vector requires about 100 multiplications.

A 100 by 100 matrix times a vector requires about 10,000 multiplications.

The important idea is:

One dot product costs O(n).

We perform n dot products.

Therefore:

n × O(n) = O(n²)

This is a very useful way to reason about complexity:

Break a large computation into smaller repeated computations.

We can now compare:

Vector addition → O(n)

Dot product → O(n)

Matrix addition → O(n²)

Matrix-vector multiplication → O(n²)

In the next post, we will take the next major step:

Matrix-matrix multiplication.

There we will see why the standard algorithm has complexity O(n³).

📘 Complexity Theory — Post 4: Complexity of Matrix Addition

In the previous post, we looked at basic vector operations and saw that vector addition, scalar multiplication, and the dot product all have linear complexity.

Now let us move from vectors to matrices.

Suppose we have two n by n matrices.

Each matrix contains:

n² entries.

To add the two matrices, we add corresponding entries one by one.

For example, if

A =
[a11 a12
a21 a22]

and

B =
[b11 b12
b21 b22]

then

A + B =
[a11 + b11 a12 + b12
a21 + b21 a22 + b22]

For a 2 by 2 matrix, we perform 4 additions.

For a 3 by 3 matrix, we perform 9 additions.

For a 10 by 10 matrix, we perform 100 additions.

In general, an n by n matrix contains n² entries.

Since we perform one addition for each entry, the total number of additions is:

n²

Therefore, the complexity of adding two n by n matrices is:

O(n²)

This is our first simple example of quadratic complexity.

Why is it quadratic?

Because the matrix grows in two directions:

n rows

and

n columns.

So the total number of positions is:

n × n = n²

This also explains an important idea:

The complexity often depends on the structure and size of the input.

A vector of length n has n entries, so many vector operations require O(n) work.

An n by n matrix has n² entries, so an operation that touches every matrix entry usually requires O(n²) work.

A useful comparison is:

Vector addition → O(n)

Matrix addition → O(n²)

If n doubles, vector addition requires roughly twice as much work.

But matrix addition requires roughly four times as much work.

For example:

10 by 10 matrix → 100 additions

20 by 20 matrix → 400 additions

40 by 40 matrix → 1600 additions

So doubling the matrix dimension multiplies the amount of work by approximately 4.

The main lesson is:

Before calculating complexity, first ask:

How many pieces of data does the input contain, and how many times do we process them?

In the next post, we will study a more interesting operation:

Matrix-vector multiplication.

There, we will see how dot products combine to produce another O(n²) algorithm.

📘 Complexity Theory — Post 3: Complexity of Basic Vector Operations

Now that we understand how common complexity functions grow, let us apply the idea to some simple mathematical operations.

We start with vectors.

Suppose we have a vector of length n:

(a1, a2, ..., an)

The value n is the input size.

The main question is:

How many elementary operations are needed when n grows?

🔹 Vector Addition

Suppose we want to add two vectors:

(a1, a2, ..., an)

and

(b1, b2, ..., bn)

We compute:

a1 + b1
a2 + b2..
an + bn

There is one addition for each position.

So the total number of additions is:

n

Therefore, vector addition has complexity:

O(n)

If the vector length doubles, the amount of work roughly doubles.

---

🔹 Scalar Multiplication

Now suppose we multiply a vector by a scalar c.

We compute:

c × a1
c × a2..
c × an

Again, there is one multiplication for each entry.

So we perform n multiplications.

Therefore, scalar multiplication also has complexity:

O(n)

---

🔹 Dot Product

Now consider the dot product of two vectors.

We calculate:

a1 × b1 + a2 × b2 + ... + an × bn

What operations are required?

We need:

n multiplications

and approximately

n - 1 additions

So the total number of elementary operations is approximately:

2n

At first, we might think the complexity should be O(2n).

But in Big-O notation, constant factors are ignored.

Therefore:

O(2n) = O(n)

So the dot product also has linear complexity.

This gives us an important lesson:

Big-O notation focuses on how the computational cost grows, not on the exact number of operations.

For example:

n operations

2n operations

5n + 10 operations

all grow linearly with n.

Therefore, all of them are classified as:

O(n)

So far, we have:

Vector addition → O(n)

Scalar multiplication → O(n)

Dot product → O(n)

In the next post, we will move from vectors to matrices and ask a very natural question:

How expensive is it to add two n by n matrices?

That will lead us naturally from O(n) to O(n²).

📘 Complexity Theory — Post 2: How Fast Do Complexity Functions Grow?

In the first post, we discussed that computational complexity tells us how the amount of work grows when the input size becomes larger.

Now let us compare some of the most common growth rates:

O(1), O(n), O(n²), O(n³), and O(2ⁿ).

The important idea is not just the formula itself, but how quickly each one grows.

Let us look at some simple values.

When n = 2:

n = 2
n² = 4
n³ = 8
2ⁿ = 4

When n = 10:

n = 10
n² = 100
n³ = 1000
2ⁿ = 1024

Now consider n = 20:

n = 20
n² = 400
n³ = 8000
2ⁿ = 1,048,576

Here we can clearly see that different complexity functions behave very differently as n becomes larger.

🔹 O(1) — Constant complexity

The amount of work does not depend on the input size.

For example, accessing one particular element of an array can be considered a constant-time operation.

🔹 O(n) — Linear complexity

The amount of work grows directly with the input size.

If n doubles, the work roughly doubles.

For example, adding two vectors of length n requires n additions.

🔹 O(n²) — Quadratic complexity

If n doubles, the amount of work becomes roughly four times larger.

This type of complexity often appears when we have to compare or process every pair of objects.

An n by n matrix, for example, contains n² entries.

🔹 O(n³) — Cubic complexity

If n doubles, the amount of work becomes roughly eight times larger.

Many classical linear algebra algorithms have cubic complexity.

Later, we will see that the standard method for multiplying two n by n matrices has cubic complexity.

🔹 O(2ⁿ) — Exponential complexity

This grows extremely quickly.

Every time n increases by 1, the amount of work roughly doubles.

For example:

2¹⁰ = 1024

2²⁰ = 1,048,576

2⁴⁰ is already greater than one trillion.

This is why exponential-time algorithms can become impractical very quickly.

A useful way to remember the growth is:

O(1) grows the slowest.

Then comes O(n).

Then O(n²).

Then O(n³).

And O(2ⁿ) grows much, much faster.

The main lesson is:

Complexity theory is about growth.

An algorithm may work perfectly well for a small input, but become extremely slow when the input size becomes large.

In the next post, we will start applying these ideas to actual mathematical operations, beginning with vectors and matrices.