From a Similarity Question to a Linear System
Suppose \(\mathbf{A}\) and \(\mathbf{B}\) are square matrices representing linear operators in different bases. To determine whether they are similar, we seek an invertible matrix \(\mathbf{P}\) that connects them by \( \mathbf{B}=\mathbf{P}^{-1}\mathbf{A}\mathbf{P}\). Directly guessing \(\mathbf{P}\) can be difficult. Multiplying this equation on the left by \(\mathbf{P}\) gives the equivalent equation \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{B}\), which is linear in the entries of \(\mathbf{P}\). We can solve that linear system first, then check whether any solution is invertible.
Throughout, let \(\mathbf{A},\mathbf{B}\in\mathbb{R}^{n\times n}\). Write the unknown matrix as \(\mathbf{P}=(p_{ij})\). For each pair of indices \(i,j\), the \((i,j)\)-entry of \(\mathbf{A}\mathbf{P}\) is \(\sum_{k=1}^{n}a_{ik}p_{kj}\), while the \((i,j)\)-entry of \(\mathbf{P}\mathbf{B}\) is \(\sum_{k=1}^{n}p_{ik}b_{kj}\). Thus, the equation \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{B}\) gives \(n^2\) scalar equations, each linear and homogeneous in the \(n^2\) unknown entries \(p_{ij}\). Homogeneous means that every equation has right-hand side zero.
To solve the equation, list the entries of \(\mathbf{P}\) as variables, form the corresponding homogeneous linear system, and row reduce its coefficient matrix. This gives all solutions, including the zero matrix. The final step is not optional: among the solutions, we must find one with nonzero determinant (equivalently, an invertible one). The solution set may contain nonzero matrices that are all singular.
Why the Equation Detects Similarity
Proof. Suppose first that \(\mathbf{A}\) and \(\mathbf{B}\) are similar. By definition, there is an invertible \(\mathbf{P}\) such that \(\mathbf{B}=\mathbf{P}^{-1}\mathbf{A}\mathbf{P}\). Multiplying on the left by \(\mathbf{P}\) gives \(\mathbf{P}\mathbf{B}=\mathbf{A}\mathbf{P}\), so the required equation holds. Conversely, suppose that \(\mathbf{P}\) is invertible and \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{B}\). Multiplying on the left by \(\mathbf{P}^{-1}\) gives \(\mathbf{P}^{-1}\mathbf{A}\mathbf{P}=\mathbf{B}\). This is precisely the relation that says \(\mathbf{A}\) and \(\mathbf{B}\) are similar. \(\square\)
The theorem explains both what the computation accomplishes and what it cannot skip. Solving the linear system finds every possible intertwining matrix, but similarity requires an invertible one. Because the equation is homogeneous, \(\mathbf{P}=\mathbf{O}\) is always a solution; its presence says nothing about whether \(\mathbf{A}\) and \(\mathbf{B}\) are similar.
Proof. The zero matrix is a solution because \(\mathbf{A}\mathbf{O}=\mathbf{O}=\mathbf{O}\mathbf{B}\). If \(\mathbf{P}_1\) and \(\mathbf{P}_2\) are solutions, then \(\mathbf{A}(\mathbf{P}_1+\mathbf{P}_2)=\mathbf{A}\mathbf{P}_1+\mathbf{A}\mathbf{P}_2=\mathbf{P}_1\mathbf{B}+\mathbf{P}_2\mathbf{B}=(\mathbf{P}_1+\mathbf{P}_2)\mathbf{B}\), so their sum is a solution. If \(c\in\mathbb{R}\) and \(\mathbf{P}_1\) is a solution, then \(\mathbf{A}(c\mathbf{P}_1)=c\mathbf{A}\mathbf{P}_1=c\mathbf{P}_1\mathbf{B}=(c\mathbf{P}_1)\mathbf{B}\), so every scalar multiple is also a solution. These are the subspace conditions. \(\square\)
Solving for an Invertible Matrix
Worked Example: Similar Diagonal Matrices in Reversed Order
Find an invertible solution of \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{B}\) for \(\mathbf{A}=\begin{bmatrix}2&0\\0&3\end{bmatrix}\) and \(\mathbf{B}=\begin{bmatrix}3&0\\0&2\end{bmatrix}\), then verify the similarity.
Set \(\mathbf{P}=\begin{bmatrix}x&y\\z&w\end{bmatrix}\). Multiplying in the two orders gives
Equating corresponding entries yields \(-x=0\), \(0=0\), \(0=0\), and \(w=0\). In the variable order \(x,y,z,w\), the nontrivial equations have coefficient matrix shown below. Scaling the first row by \(-1\) gives its reduced row echelon form:
Therefore \(x=w=0\), while \(y,z\) are free. The entire solution family is \(\mathbf{P}=\begin{bmatrix}0&y\\z&0\end{bmatrix}\). Its determinant is \(-yz\), so it is invertible whenever both \(y\ne0\) and \(z\ne0\). Choose \(y=z=1\), giving \(\mathbf{P}=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Its inverse is itself, since \(\mathbf{P}^2=\mathbf{I}_2\).
Check: Direct multiplication gives \(\mathbf{A}\mathbf{P}=\begin{bmatrix}0&2\\3&0\end{bmatrix}=\mathbf{P}\mathbf{B}\). Also, \(\mathbf{P}^{-1}\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{A}\mathbf{P}=\begin{bmatrix}3&0\\0&2\end{bmatrix}=\mathbf{B}\). Thus the chosen solution verifies the claimed similarity.
This example illustrates why the whole solution family is useful. Row reduction identifies the free entries; the determinant then tells us which choices produce an invertible matrix. A nonzero solution is not automatically a suitable change-of-basis matrix.
Nonzero Solutions May All Be Singular
Worked Example: A Nonzero Solution That Does Not Prove Similarity
For \(\mathbf{A}=\mathbf{I}_2\) and \(\mathbf{B}=\begin{bmatrix}1&0\\0&2\end{bmatrix}\), solve the equation and determine whether any solution is invertible.
Again write \(\mathbf{P}=\begin{bmatrix}x&y\\z&w\end{bmatrix}\). Then \(\mathbf{A}\mathbf{P}=\begin{bmatrix}x&y\\z&w\end{bmatrix}\) and \(\mathbf{P}\mathbf{B}=\begin{bmatrix}x&2y\\z&2w\end{bmatrix}\). Equating entries gives \(y=0\) and \(w=0\), with no restrictions on \(x,z\). The coefficient matrix for these equations, in the order \(x,y,z,w\), reduces as follows:
Thus every solution has the form \(\mathbf{P}=\begin{bmatrix}x&0\\z&0\end{bmatrix}\). Its determinant is \(x\cdot0-0\cdot z=0\) for every choice of \(x,z\). For example, taking \(x=1,z=0\) gives the nonzero solution \(\begin{bmatrix}1&0\\0&0\end{bmatrix}\), but that matrix is singular. No solution is invertible, so the theorem shows that \(\mathbf{A}\) and \(\mathbf{B}\) are not similar.
Check: For the displayed nonzero solution, both \(\mathbf{A}\mathbf{P}\) and \(\mathbf{P}\mathbf{B}\) equal \(\begin{bmatrix}1&0\\0&0\end{bmatrix}\), as required. The equation is satisfied, but the determinant is zero, so this solution cannot be used in \(\mathbf{P}^{-1}\mathbf{A}\mathbf{P}\).
The example separates two questions: does the homogeneous system have a nonzero solution, and does it have an invertible solution? The first is answered by row reduction alone. The second requires examining the matrices in the solution family.
When the Homogeneous System Has Only the Zero Solution
Worked Example: No Nonzero Intertwining Matrix
For \(\mathbf{A}=\begin{bmatrix}1&0\\0&2\end{bmatrix}\) and \(\mathbf{B}=\begin{bmatrix}3&0\\0&4\end{bmatrix}\), show that no nonzero solution exists.
Let \(\mathbf{P}=\begin{bmatrix}x&y\\z&w\end{bmatrix}\). The products are \(\mathbf{A}\mathbf{P}=\begin{bmatrix}x&y\\2z&2w\end{bmatrix}\) and \(\mathbf{P}\mathbf{B}=\begin{bmatrix}3x&4y\\3z&4w\end{bmatrix}\). Equating entries gives \(-2x=0\), \(-3y=0\), \(-z=0\), and \(-2w=0\). Each coefficient is nonzero, so \(x=y=z=w=0\). The only solution is \(\mathbf{P}=\mathbf{O}\), which is not invertible.
Check: Substituting \(\mathbf{P}=\mathbf{O}\) gives \(\mathbf{A}\mathbf{P}=\mathbf{O}=\mathbf{P}\mathbf{B}\). Since this is the only solution, there is no invertible solution, and the matrices are not similar.
This case differs from the preceding example. There, nonzero solutions existed, but every one was singular. Here, the solution set contains no nonzero matrix at all. Both situations rule out similarity, but they are different outcomes of the linear system.
A Reliable Procedure and a Common Pitfall
Write \(\mathbf{P}=(p_{ij})\) with \(n^2\) unknown entries.
Compute \(\mathbf{A}\mathbf{P}\) and \(\mathbf{P}\mathbf{B}\), then equate entries in corresponding positions.
Row reduce its coefficient matrix and express every solution using its free variables.
Choose values for the free variables that make \(\det\mathbf{P}\ne0\), if such values exist.
Check \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{B}\), and then compute \(\mathbf{P}^{-1}\mathbf{A}\mathbf{P}\) to confirm it equals \(\mathbf{B}\).
Common pitfall: treating any nonzero solution as a similarity matrix. For \(\mathbf{A}=\mathbf{I}_2\), \(\mathbf{B}=\begin{bmatrix}1&0\\0&2\end{bmatrix}\), and \(\mathbf{P}=\begin{bmatrix}1&0\\0&0\end{bmatrix}\), the equation is indeed satisfied: \(\mathbf{A}\mathbf{P}=\begin{bmatrix}1&0\\0&0\end{bmatrix}=\mathbf{P}\mathbf{B}\). The incorrect conclusion is that \(\mathbf{A}\) and \(\mathbf{B}\) must therefore be similar. In fact, \(\det\mathbf{P}=0\), so \(\mathbf{P}^{-1}\) does not exist. The correction is to test invertibility after solving, not merely to find a nonzero matrix.
When row reduction gives a family \(\mathbf{P}=c_1\mathbf{P}_1+\cdots+c_r\mathbf{P}_r\), the remaining task is to choose coefficients \(c_1,\dots,c_r\) so that the resulting matrix has nonzero determinant. If a candidate works, multiplying back verifies it. If every solution is singular, or the only solution is zero, then no similarity matrix exists. The equation \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{B}\) therefore gives a systematic search: linear algebra describes all candidates, and invertibility determines which candidates can implement the change of basis.
Check Your Understanding
For each problem, distinguish solving the equation from checking whether a solution is an invertible similarity matrix.
- For \(\mathbf{A}=\begin{bmatrix}1&0\\0&3\end{bmatrix}\) and \(\mathbf{B}=\begin{bmatrix}3&0\\0&1\end{bmatrix}\), solve \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{B}\) and give an invertible solution.
- Explain why a nonzero solution of \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{B}\) is not by itself enough to prove that \(\mathbf{A}\) and \(\mathbf{B}\) are similar.
- For \(\mathbf{A}=\mathbf{I}_2\) and \(\mathbf{B}=\begin{bmatrix}2&0\\0&2\end{bmatrix}\), find the full solution family and determine which members are invertible.
- State and prove the two implications in the equivalence between similarity and the existence of an invertible solution to \(\mathbf{A}\mathbf{P}=\mathbf{P}\mathbf{B}\).
