Is basis change ever useful in practical linear algebra?

In layman's terms, why would anyone ever want to change basis? Do eigenvalues have to do with changing basis?

• There are so many reasons, I doubt you'll see all of them in just one answer. Here is just one: en.wikipedia.org/wiki/Principal_component_analysis – David K Apr 13 '16 at 1:44
• A relatively esoteric example (see my comment): math.stackexchange.com/questions/654765/sum-of-polynomial. – Martín-Blas Pérez Pinilla Apr 13 '16 at 6:14
• You prove the Master Theorem this way. – djechlin Apr 13 '16 at 13:39
• Rotation is essentially a change of basis. If you ever employed a linear coordinate change, you changed bases. – fourierwho Apr 13 '16 at 18:00
• Here's a very simple layman's example: let's say you have a cube that's rotated arbitrarily and isn't orthogonal the coordinate axes, and you're trying to determine if a point is inside of it. That's a bit tricky to determine directly. If you can change to a basis where the cube is orthogonal to the coordinate axes, determining if the point is inside becomes trivial. – Andy Apr 14 '16 at 0:51

Changing basis allows you to convert a matrix from a complicated form to a simple form. It is often possible to represent a matrix in a basis where the only nonzero elements are on the diagonal, which is exceptionally simple. These diagonal elements will be the eigenvalues of the matrix. This is especially helpful in solving linear systems of differential equations. Often in physics, engineering, logistics, and probably lots of other places, you have a system of differential equations which all depend on each other. In order to solve the system directly, you would have to solve all equations at once, which is hard. We can use matrices to describe this system. By changing basis, you may be able to make that matrix diagonal, which effectively separates the differential equations from each other, so you can solve just one at a time. This is comparatively easy. Situations where I know this comes up are:

• Quantum mechanics, solving the Schrodinger equation to describe the state of matter on the quantum level.
• Electrical engineering, understanding the time-evolution of an electrical circuit.
• Mechanical engineering, understanding the motion of a linear mechanical system, such as multiple spring-mass system.

Edit:

Here is another very important reason for change of basis I just remembered: suppose you have a matrix $A$, and you want to calculate $A^n$ for some large $n$. This takes a while, even for computers. But, if you can find a change of basis matrix $P$ so that $A=P^{-1}DP$ for a diagonal matrix $D$, then $$A^n=P^{-1}DPP^{-1}DPP^{-1}DP...P^{-1}DP.$$ All of the terms $PP^{-1}$ are the identity, so we get $$A^n=P^{-1}D^nP.$$ Powers of diagonal matrices are really easy: just raise each diagonal element to the $n$th power. So this method allows us to find powers of matrices very easily. When would we ever want to take large powers of matrices? Whenever finding numerical solutions to differential equations, partial or ordinary. This comes up all the time, so we are glad that we can change bases!

• Not just for powers; in fact, this can be used anytime one wants to evaluate a function with matrix arguments, like the exponential or the sine. In the nondiagonalizable case, one has to be content with the Jordan form. – J. M. isn't a mathematician Apr 13 '16 at 21:35

Changing basis can make it easier to understand a given linear transformation.

Suppose $T:V \to V$ is a linear transformation. It may seem difficult to understand or to visualize what effect $T$ has when it is applied to a vector $x$. However, suppose we are lucky enough to find a vector $v$ with the special property that $T(v) = \lambda v$ for some scalar $\lambda$. Then, it's easy enough to understand what $T$ does to $v$, at least.

Suppose we are lucky enough to find an entire basis $\{v_1,\ldots,v_n\}$ of these special vectors. So $T(v_i) = \lambda_i v_i$, for some scalars $\lambda_i, i =1,\ldots,n$. Given any vector $x$, we can write $x$ as a linear combination of the vectors $v_i$: $$x = c_1 v_1 + \cdots + c_n v_n.$$ And now it seems easier to think about $T(x)$: \begin{align} T(x) &= c_1 T(v_1) + \cdots + c_n T(v_n) \\ &= c_1 \lambda_1 v_1 + \cdots + c_n \lambda_n v_n. \end{align} That is fairly simple. Each component of $x$ (with respect to our special basis) simply got scaled by a factor $\lambda_i$.

So if we can find a basis of eigenvectors for $T$ (and often we can), then it helps us to understand $T$.

By the way, one great practical example of a change of basis is computing a convolution efficiently using the fast Fourier transform (FFT) algorithm. Any discrete convolution operator is diagonalized by a special basis, the discrete Fourier basis. So, to perform a convolution on an image (in image processing), you take the FFT of the image (you change basis to the Fourier basis), then you multiply pointwise by the eigenvalues of the convolution operator, then you take the inverse FFT (change back to the standard basis). This approach is much, much faster than performing convolution in the space domain.

You may have noticed multiplying matrices can be hard. By changing bases, we can make it easier.

• If you first change the basis, second multiply, would you have to unchange the basis (reversal) after multiplication to get the standard form of the matrix product? – Grau Apr 13 '16 at 1:51
• @Grau - Yes, see Ales S's answer. – Karlo Apr 13 '16 at 9:16

Singular Value Decomposition, which is one of the most widely-used techniques in numerical computing, is a basis-change. It takes a linear transformation, and does a basis change on both the input space and the output space so that the transformation becomes just multiplication with no addition (ie a diagonal matrix).

This uncovers a lot of useful information about the transformation such as which input variables play the biggest role, how correlated they are to each other, whether there are any irrelevant variables, etc. It is pretty much the sledge-hammer for doing numerical computing with matrices.

Linear algebra is all about basis-change. Matrices are change of basis machines !

When you form a linear combination $a\vec u+b\vec v+\cdots c\vec w$, you can see it as the vector $(a,b,\cdots c)$ expressed in the basis $(\vec u,\vec v,\cdots \vec w)$.

For the same reason, a matrix product $AB$ expresses what the matrix $A$ becomes when applied to the vectors of the matrix $B$. And think that most matrix operations can be described as products of elementary transforms (which are changes of basis involving one axis or two).

Looking at the resolution of a system of linear equations, you can see it as a change of basis such that the hyperplanes corresponding to the equations become parallel to the axis, so that computing their intersections becomes trivial.

And so on, and so on.

The Eigendecomposition is indeed a convenient way to characterize a change of basis, as it finds the directions that are left unchanged by the transforms (the axis that are mapped onto themselves). These special directions are indeed quite interesting as the behavior of the transform is very simple there (just a scalar product).

Rotations are a particularly important class of transformations, as they preserve distances and cause no deformation (they are so-called "rigid-body" transforms). The Eigendecomposition expresses that any (diagonizable) transform can be seen as a rotation that aligns the Eigendirections with the axis, followed by a (possibly anisotropic) stretching of the axis, followed by the inverse rotation.

The Eigendecomposition generalizes as the Singular Value decomposition. It allows the two spaces to have differing dimensions, but still decomposes a transform as a sequence of rotation/scaling/rotation.

The Singular Values fully characterize the resizing/deformation (and possible loss of dimensions), giving a very synthetic view on the transform.

• "Matrices are changes of basis !" I'm uncomfortable with this - a matrix is an array of numbers (or more generally elements of a ring). In advanced linear algebra when working with modules we don't always have a basis, yet matrices still exist. – user223391 Apr 13 '16 at 21:36
• @ZacharySelk: obviously this is an informal statement intended to stimulate the OP's intuition. You can raise similar objections for all sentences in my answer. In particular, matrices, linear transformations and changes of basis are freely mixed up. – Yves Daoust Apr 13 '16 at 22:27
• Yes this is an informal statement, but I have been uncomfortable with that type of intuition. I remember learning linear algebra and statements like "matrices are linear transformations/changes of basis" etc. were really confusing to me and made linear algebra way harder. I am not the downvoter, btw. I think your answer is good. But it would have been very confusing for me, and I assume other people just learning linear algebra as well. But maybe it is helpful for OP! – user223391 Apr 13 '16 at 22:37
• @ZacharySelk: very slightly reworded. Hope not worse like this :) – Yves Daoust Apr 13 '16 at 22:40
• It's up to you. Either way +1 – user223391 Apr 14 '16 at 0:44

$$\sum_{k=0}^{n-1}k^3 = \sum_{k=0}^{n-1}6\binom k3+6\binom k2 + \binom k1 = 6\binom n4+6\binom n3 + \binom n2=\frac{n^4-2n^3+n^2}4.$$ Hey, that change of basis in the space of polynomials was useful.

It's used to prove the Master Theorem. Diagonal matrices are very easy to take powers of ($diag(a_1,\ldots,a_n)^k = diag(a_1^k, \ldots, a_n^k)$) and we have $(PAP^{-1})^k = PA^kP^{-1}$. The Master Theorem relies on changing to a diagonal basis, taking a large power, and changing back.

At the least, try working out the explicit formula for the Fibonacci numbers this way.

• Any branch of mathematics may have its own "Master Theorem". (MacMahon's Master Theorem; Ramanujan's master theorem, etc.). Why is this branch arrogant enough to assume everyone knows which one we mean? – GEdgar Apr 13 '16 at 17:51
• @GEdgar totally agree, and I have no idea how they got away with it. Actually I do, probably that it became popular in competition math and high school / college students like posting on the Internet a lot. Here, for instance. That's just conjecture though. – djechlin Apr 13 '16 at 17:53
• which master theorem? the wiki link is ambiguous – baxx Jun 28 '20 at 13:00

Note that the Fourier transform is simply a change of basis. It is entirely possible you're actually reading this very answer thanks to change of basis. Check out https://en.wikipedia.org/wiki/Orthogonal_frequency-division_multiplexing for instance. Edit: it might be weird to see the connection if you're just starting out with linear algebra. In signal processing among other fields, we generalize the notion of vectors in such a way that functions can also be seen as vectors. Starting from this idea, it might not be so weird to talk about basis changes for functions - which is exactly what the Fourier transform does. Indeed, this is what Taylor expansions does as well in a sense.

Another thing, in wireless communications with multiple transmitter/receiver antenna systemes (MIMO) it's very common to model the multiplicative noise in the channel as a linear transformation, i.e. the received signal is given by $\textbf{y} = H\textbf{x}$ (plus additive noise). I.e. there is one noisy channel for every pair of transmitter/receiver antennas. But by the singular value decomposition, we can find the appropriate change of basis for the transmitted signal that makes it "orthogonal to the channel" in the sense that $H$ is diagonal. This helps throughput lot.

Structural dynamics with the Finite Element Method

Computing the dynamic response of a structure is done with modal analysis.

The original vector space is displacements and rotations in each node. These are unsuited to dynamic response. The system of equations is therefore transformed into a new vector space where each element in the vector space represents a vibration mode.

Wikipedia has some nice animations of vibration modes, ordered from lowest to highest frequency:

Each mode (eigenvector) is the vibration to a specific frequency (eigenvalue). When these have been found, we can compute interesting stuff like the structural response to an earthquake of a certain frequency spectrum. Afterwards, the basis is changed back to the original to obtain forces and displacements in each node.

Practical speed related aspects Matrix multiplication and division and equation system solving can become much faster to perform in some bases than others. Often one can cut the algorithmic complexity so much that it becomes a difference between something being practically useful or far too slow for usefulness. The reason for this is that the underlying field of elements provides $1$ and $0$ elements which by definition make multiplication and addition simpler. $$\text{field properties for the elements 1 and 0 utilizable for saving calculations}\begin{cases}a \cdot 0 &= 0\\ a + 0 &= a\\a\cdot 1 &= a\end{cases}$$

The first two together lets us ignore whole parts of scalar products with zero elements which is the main gain. Then the third one allows us to avoid multiplications which can be nice as in computers adding is less computationally complex than multiplying, saving hardware on the chip or clock cycles.

$${\bf D} = \left(\begin{array}{ccccc} d_1&0&0&\cdots&0\\0& d_2 & 0 &\cdots & 0\\0&0&\ddots& \ddots &0\\0&0&\ddots&d_{n-1}&0\\0&0&\cdots&0&d_n\end{array}\right) \hspace{1cm} {\bf C} = \left(\begin{array}{ccccc} {\bf C_1}&\bf 0&\bf 0&\cdots& \bf 0\\\bf 0& \bf C_2 & \bf 0 &\cdots & \bf 0\\ \bf \bf 0&\bf 0&\ddots& \ddots &\bf 0\\\bf 0&\bf 0&\ddots& \bf C_{n-1}&\bf 0\\\bf 0&\bf 0&\cdots&\bf 0&\bf C_n\end{array}\right) \hspace{1cm}$$ Diagonal matrix to the left, only n non-zero values - the ones on the diagonal. Block-diagonal matrix to the right. The $\bf C_k$ matrices on the diagonal are square and by properties of matrix multiplication will multiply onto their own position only. The larger we can make these $\bf 0$ matrices the more time we can save when doing computations.

Theory understanding aspects Basis change is the basis of understanding more advanced algebra. Eigenvalues, eigenvectors and matrix diagonalization are the first "steps" to that. Then canonical bases of various kinds and matrix representation of groups and fields with simultaneous block-diagonalizations ( that a set of matrices which multiply onto each other can be put on the same block-diagonal form ). Can be used to create an understanding and a framework for systematic work on these more advanced algebras.