When can two matrices have zero diagonal in the same basis? It's common to ask if two Hermitian matrices $A$ and $B$ can be diagonalized in the same basis. Is there an efficient way to check if they can be made hollow in the same basis? By hollow, I mean that the diagonal elements are all $0$. As esoteric as this sounds, I've had it come up in an experimentally relevant physics problem.
Potentially useful aspects I have understood so far (I am only concerned with Hermitian matrices):


*

*$A$ can be transformed into a hollow matrix iff $\operatorname{Tr}[A]=0$ (see this post)

*To find a basis in which $A$ is hollow, find a non-degenerate, full rank Hermitian matrix $Q$ that satisfies $\operatorname{Tr}[A Q^N] = 0$ for $N=0,\ldots,\dim(A)-1$. $A$ is hollow in the eigenbasis of $Q$.


In principle, the second fact could be used to solve the problem, however I would like a method to check if a solution exists that is simpler than finding the solution, analogous to how $AB-BA = 0$ tests if $A$ and $B$ can be simultaneously diagonalized.
 A: This is still a long ways off from your goal of a simple characterization for this, but I think it may highlight some of the important considerations. Let $A$ be a symmetric hollow matrix with eigendecomposition $A=UDU^{*}$, $\text{diag}(D)=\vec{\lambda},$ which without loss of generality we take to be ordered such that $\lambda_{1}\leq \lambda_{2}\leq\cdots\leq \lambda_{n}.$ If $V$ is any unitary matrix, then \begin{align}(V^{*}AV)_{i,i}&=((V^{*}U)D(U^{*}V))_{i,i}\notag\\&=\sum_{j=1}^{n}\lambda_{j}|\langle v_{i},u_{j}\rangle|^{2}\notag\\&=\sum_{j=1}^{n}\lambda_{j}S_{i,j}=(S\vec{\lambda})_{i},\label{eq1}\end{align} where $S=[|\langle v_{i},u_{j}\rangle|^{2}]_{i,j=1}^{n}$ is doubly-stochastic. Then $V^{*}AV$ remaining hollow is equivalent to $S\vec{\lambda}=0,$ which in the case $n=2,$ combined with the doubly-stochastic criteria, forces $V$ to be of the form $P\Delta,$ where $P$ is a permutation matrix, and $\Delta$ is a diagonal matrix with diagonal entries of modulus $1$ (it is clear that if $A$ is hollow, then $V^{*}AV$ is hollow for $V$ of this form for any $n,$ but in the $n=2$ case, this becomes necessary so long as $A\neq0$).
In one special case, we can see that there is a nontrivial collection of unitary matrices which preserve the hollowness of $A:$ If $A$ has eigenvalues with multiplicities $>1,$ then the eigendecomposition is not unique, and $A=WDW^{*}$ for a unitary $W$ if and only if $W=U\left(\bigoplus_{j=1}^{k}V_{j}\right),$ where the direct sum is partitioned conformally to $D$ and the $V_{j}$ matrices are all unitary. Then if $V=U\left(\bigoplus_{j=1}^{k}V_{j}^{*}\right)U^{*},$ $V^{*}AV=A$ is hollow, as is $(V')^{*}AV'$ for $V'=VP\Delta$ for $V$ in this form, and any $P\Delta$ as above.
It's also worth noting that $\{S\vec{\lambda}:S\text{ is doubly-stochastic}\}$ is exactly the set of vectors that majorize $\vec{\lambda}$ (I'll define this in a second). First note that we may consider these to be ordered such that $(S\vec{\lambda})_{1}\leq (S\vec{\lambda})_{2}\leq\cdots\leq (S\vec{\lambda})_{n},$ since otherwise $PS\vec{\lambda}$ has this property for some permutation matrix $P$, and we can arrive at $PS$ by considering $V'=VP$ in Equation (\ref{eq1}). I'll say that $x$ majorizes $y$ (for two real vectors $x,y$ with their entries in increasing order) when for each $1\leq k\leq n,$ $\sum_{i=1}^{k} x_{i}\geq \sum_{i=1}^{k} y_{i},$ with equality when $k=n.$ In other words, $x$ is "flatter" than $y,$ and they have the same sum. Let $L$ be the set $$\{S\vec{\lambda}:S\text{ is doubly-stochastic and }S\vec{\lambda}\text{ is in increasing order}\}.$$ Then $L$ is convex, since the set of doubly-stochastic matrices is, and the increasing order property is preserved by convex combinations. Then the $0$ vector is an extreme point of this set: if $0=\alpha x+(1-\alpha)y,$ $x,y\in L,$ and $\alpha\in[0,1],$ where $x$ and $y$ are not the zero vector, then since for the vector of all ones $e$, $e^{T}x=e^{T}S\vec{\lambda}=e^{T}\vec{\lambda}=0,$ $x_{1}<0$ (and similarly $y_{1}<0);$ so $0=\alpha x_{1}+(1-\alpha)y_{1}<0,$ which is a contradiction. If we remove the ordering restriction on $L,$ it's no longer clear whether or not $0$ is an extreme point, however.
We can also observe that the set of doubly-stochastic $S$ such that $S\vec{\lambda}=0$ is convex, and when $\vec{\lambda}\neq0$, it does not contain any of the permutation matrices (which are the vertices of the polytope of doubly-stochastic matrices). The trouble with this direction is that for a convex combination of $S_{1}$ and $S_{2}$, there is no clear way (to me) to select $V$ such that $[|\langle v_{i},u_{j}\rangle|^{2}]_{i,j=1}^{n}$ is equal to this convex combination, even given such a $V$ for $S_{1}$ and $S_{2}.$
A last comment: if in addition $A$ is circulant, then it is hollow automatically, so in the general case, if $V=UF^{*},$ for the DFT matrix $F,$ then $V^{*}AV$ will be circulant and hollow.
