Is basis change ever useful in practical linear algebra?

Question

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

Answer 1

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!

Answer 2

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$: \begin{equation} x = c_1 v_1 + \cdots + c_n v_n. \end{equation} 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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

\begin{equation} \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. \end{equation} Hey, that change of basis in the space of polynomials was useful.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

Solid mechanics. Computing the principal stresses/strains in a material involves a change of basis. With the principal stresses, we can compute the maximum normal stress and maximum shear stress the material experiences. And these maxima tell us whether the material will become damaged or not.