[proofplan]
Any reordering of the $N$ grid points is a permutation $\pi \in S_N$ of the basis vectors $\{e_1, \ldots, e_N\}$. The associated permutation matrix $P$ satisfies $P^\top = P^{-1}$ (it is orthogonal), and conjugation $P^\top A P$ expresses the same linear operator in the reordered basis. Since $A^*$ is defined as the matrix of the five-point stencil with respect to the reordered basis, the identity $A^* = P^\top A P$ follows directly from the change-of-basis formula for matrix representations of linear maps.
[/proofplan]
[step:Associate a permutation matrix to the reordering and verify it is orthogonal]
Let $N = m^2$ denote the total number of interior grid points. The natural ordering assigns to each grid point $(i, j)$ a basis vector $e_k \in \mathbb{R}^N$ for some $k \in \{1, \ldots, N\}$. Any alternative ordering is a bijection $\pi: \{1, \ldots, N\} \to \{1, \ldots, N\}$ (a permutation) that reassigns the indices.
Define the permutation matrix $P \in \mathbb{R}^{N \times N}$ by
\begin{align*}
P_{ij} = \begin{cases} 1 & \text{if } j = \pi(i), \\ 0 & \text{otherwise.} \end{cases}
\end{align*}
Equivalently, $P e_i = e_{\pi(i)}$ for each $i$, so $P$ maps each natural-ordering basis vector to the corresponding reordered basis vector. The matrix $P$ is a permutation matrix, with exactly one entry equal to $1$ in each row and each column, and all other entries equal to $0$. The columns of $P$ are distinct standard basis vectors, so they form an orthonormal set:
\begin{align*}
(P^\top P)_{ij} = \sum_{k=1}^N P_{ki} P_{kj} = \delta_{\pi^{-1}(i), \pi^{-1}(j)} = \delta_{ij}.
\end{align*}
Therefore $P^\top P = I$, i.e., $P$ is an orthogonal matrix with $P^{-1} = P^\top$.
[/step]
[step:Apply the change-of-basis formula to obtain $A^* = P^\top A P$]
The matrix $A$ represents the five-point stencil as a linear map
\begin{align*}
T: \mathbb{R}^N &\to \mathbb{R}^N
\end{align*}
with respect to the natural-ordering basis $\{e_1, \ldots, e_N\}$. That is, the entry $A_{ij}$ equals the coefficient of $e_i$ in $T(e_j)$, or equivalently $A_{ij} = e_i^\top T(e_j)$.
Under the reordered basis $\{e_{\pi(1)}, \ldots, e_{\pi(N)}\} = \{Pe_1, \ldots, Pe_N\}$, the same linear map $T$ has matrix representation
\begin{align*}
(A^*)_{ij} = (Pe_i)^\top T(Pe_j) = e_i^\top P^\top T(Pe_j).
\end{align*}
Since $T$ acts on coordinates via $A$ (i.e., the coordinate vector $v$ maps to $Av$ in the natural basis), we have $T(Pe_j) = A(Pe_j)$, reading $P e_j$ as a coordinate vector in the natural basis. Therefore:
\begin{align*}
(A^*)_{ij} = e_i^\top P^\top A P e_j = (P^\top A P)_{ij}.
\end{align*}
This holds for all $i, j \in \{1, \ldots, N\}$, so $A^* = P^\top A P$.
Since $P$ is orthogonal ($P^\top = P^{-1}$), the matrix $P$ satisfies the stated conclusion.
[guided]
The key insight is that the five-point stencil defines a single linear map $T: \mathbb{R}^N \to \mathbb{R}^N$ (given by the stencil applied to the grid function), and the matrices $A$ and $A^*$ are simply two different matrix representations of this same map, one for each ordering of the grid points.
The standard change-of-basis formula from linear algebra states: if $A$ is the matrix of $T$ with respect to a basis $\mathcal{B}$, and $P$ is the matrix whose columns express a new basis $\mathcal{B}'$ in terms of $\mathcal{B}$, then the matrix of $T$ with respect to $\mathcal{B}'$ is $P^{-1} A P$.
In our setting, $\mathcal{B} = \{e_1, \ldots, e_N\}$ (natural ordering) and $\mathcal{B}' = \{e_{\pi(1)}, \ldots, e_{\pi(N)}\}$ (new ordering). The transition matrix $P$ satisfies $Pe_i = e_{\pi(i)}$, expressing each new basis vector as a member of the old basis. Since permutation matrices are orthogonal, $P^{-1} = P^\top$, so the new matrix is $P^\top A P = A^*$.
Why must $P$ be orthogonal? Because permutation matrices permute the standard basis vectors, they preserve inner products: $\langle Pe_i, Pe_j \rangle = \langle e_{\pi(i)}, e_{\pi(j)} \rangle = \delta_{\pi(i), \pi(j)} = \delta_{ij}$. Equivalently, the columns of $P$ are orthonormal, which is the defining property of an orthogonal matrix.
One consequence of $A^* = P^\top A P$ with $P$ orthogonal is that $A$ and $A^*$ have the same eigenvalues, the same determinant, the same trace, and the same singular values. The ordering of grid points is a labelling convention and does not affect the spectral properties of the discretisation.
[/guided]
[/step]
