Reducing computation required for Linear Transformations.

Demonstrating how use of eigen basis as coordinate system makes linear transformations more efficient and less time consuming.

For a Linear transformation T : ℝⁿ → ℝⁿ
We require a matrix A called transformation matrix, such that T(x)=Ax.

Here matrix A is a dense matrix and it becomes huge for large value of n. When we need to transform a vector x to T(x) many times then we have to apply matrix A again and again which makes the computations very high. Therefore we need to optimize this process and find a more efficient way of implementing this task.

To reduce the computations, we change the coordinate system of x from standard basis to eigen basis.

Whole process to reduce the computations required in linear transformation is shown in the above figure where D represents a Diagonal matrix.

This process has 3 major steps-

Now we will see each step of the process in detail.

Vector x can be written as linear combination of vectors v₁, v₂, v₃…vₙ —

We also know that -

From equation 1 and equation 2, we can write vector x in standard basis as -

We assume that A has n linearly independent eigen vectors.

Therefore, we can say that -

It can be written as -

which is similar to equation 1 and therefore we can write the transformation of the given vector in eigen basis as —

Similarly,

Also,

Using the same concept, we can write vectors v₁, v₂, v₃…vₙ in eigen basis —

Now, combining equations 4 and equations 5, transformation of vectors v₁, v₂, v₃…vₙ in eigen basis can be written as-

From equations 6 —

As it can be seen in matrix D, all elements are zero except the diagonal (here diagonal elements are nothing but eigen values). The benefit of having a diagonal matrix is that computations are very less while multiplying it with some other matrix (only n computations) while compared to multiplication of a dense matrix like matrix A which is of the order O(N³).

Finally transformation of x in eigen basis can easily be converted to transformation of x in standard basis by using —

To reduce the computation power required for linear transformations, we can convert the given vector in standard basis to vector in eigen basis and then apply a diagonal matrix D which contains nothing but eigen values as its diagonal elements. Therefore we require only eigen values to perform the transformation. Finally the transformation of given vector in eigen basis is converted back to standard basis to achieve the desired transformation.

The benefit of doing all this is that a diagonal matrix takes very less computation power while multiplying it with some other matrix (order of n) whereas multiplication of a dense matrix like matrix A has a complexity of O(N³).

Related posts:

You have a great idea. You have a dedicated co-founder. You have a product. But you don’t yet have a company. The first big challenge you’re going to face after building your product is scraping…

This includes plans for a cultural mega-city in Riyadh (reportedly double the size of Orlando’s Disney World), a futuristic Red Sea beach resort, and the rehabilitation of UNESCO World Heritage…

As soon as a hungry dog gets food, it hurriedly consumes everything presented to it without caring that tomorrow it will still be in the same condition. This is the case to most humans, we often live…