I was trying to answer the question of whether the diagonalization of a matrix is unique and found that it is "unique up to a permutation of the entries." (see: Is a diagonalization of a matrix unique?)
However, I found a slightly different way to diagonalize A, which I think does not depend on eigenvalues.
Conjugacy (A-orthogonality) is defined such that for a matrix A the directions $p_i$ for i=1,...,n satisfy $$p_i^TAp_j = 0 \; \text{if} \; i\neq j $$
Let $$ P = [p_1 \; p_2 \; ... \; p_n] $$
So, $ P^TAP $ is a diagonal matrix.
Since we have found a way to diagonalize A without using eigenvectors and the diagagonal matrix does not depend on eigevalues, I was wondering why we can say that matrix diagonalization is "unique up to a permutation of the entries."
Doesn't this also contradict this answer: Is it possible to diagonalize a matrix without eigenvalues?
In a diagonalization, the matrix that is multiplied from the left must be the inverse of the matrix that is multiplied from the right. In your case, $P^T=P^{-1}$ does not necessarily hold. If it does, then the diagonal matrix will contain the eigenvalues.