# How to prove that the normalizer of diagonal matrices in $GL_n$ is the subgroup of generalized permutation matrices?

I'm trying to prove that de normalizer $N(T)$ of the subgroup $T\subset GL_n$ of diagonal matrices is the subgroup $P\in GL_n$ of generalized permutation matrices. I guess my biggest problem is that I don't really know how diagonal and permutation matrices (don't) commute. Because it is not true that $DM=MD$ when $D\in T$ and $M\in P$ since the permutation is either horizontal or vertical, but sometimes it seems like you can do something like it.

So far, I have proved that $P\subset N(T)$, in the following way. Let $M_\sigma\in P$. Then $M_\sigma=VS_\sigma$, with $V\in T$ and $S_\sigma$ a permutation matrix. So $M_\sigma DM^{-1}=VS_\sigma D S_\sigma^T V^{-1}$. Thus if we prove that $S_\sigma D S_\sigma^T$ is diagonal we are done. This is true since $S_\sigma D S_\sigma^T=(x_1 e_{\sigma(1)} \dots x_n e_{\sigma(n)}) (e_{\sigma^{-1}(1)} \dots e_{\sigma^{-1}(n)})=(x_{\sigma^{-1}(1)}e_1 \dots x_{\sigma^{-1}(n)}e_n)$, where $e_i$ are the standard basis vectors. Even this is hopelessly written out. I'm trying to find a way to see what the product $S_\sigma D S_\sigma^T$ is without writing it in vectors.

For the other way around I don't really know what to do. I'm having a hard time rewriting matrix products in a useful way. Perhaps there is a way of proving this using something completely different? Maybe you can prove it using $N(T)/T\simeq S_n$, but this actually what I want to use my question for. When I just write what I know about a matrix $M\in N(T)$ I just get a big system of equations that isn't really handy.

-
Try taking a matrix in $N(T)$, testing it on the diagonal matrices with zeros in all but one diagonal entry, and forcing it to be a generalized permutation matrix. Recall that the group $GL_{n}$ lives inside a ring of matrices (i.e. use addition and distributivity). –  Isaac Solomon Feb 12 '12 at 19:33
@IsaacSolomon Thanks, but I don't really understand it. When I take $D_1$ for instance (with zeroes everwhere but $D_{1,1}$), and I look at $MD_1=SM$ for some diagonal matrix $S$, I can see that it follows that the first column only has one non-zero entry. But now how do I put that together. I can write $M(x_1D_1 + \dots + x_nD_n)=SM$, but then I get confused. –  dropfruitduo Feb 12 '12 at 20:09

Let $S\in N(T)$. Then $SDS^{-1}$ is diagonal for each diagonal matrix $D$. Now, conjugation preserves the spectrum, which is exactly the diagonal in the case of diagonal matrices. So the diagonal of $SDS^{-1}$ has to be the same as the diagonal of $D$ up to a permutation. From this it's not hard to setup the equations to see that $S$ has to have a unique nonzero entry per row and column, i.e. $S$ is a generalized permutation matrix.

Concretely, let us write $\{E_{kj}\}$ for the set of canonical matrix units (i.e. $E_{kj}$ is the matrix with a $1$ in the $k,j$ position and zeroes elsewhere). Let $D=E_{11}+2E_{22}+\cdots+n E_{nn}$ (i.e. a diagonal matrix with all different entries). From the first paragraph, we know that $SDS^{-1}$ is $W=\sigma(1)E_{11}+\cdots+\sigma(n)E_{nn}$ for some permutation $\sigma$. Since $SD=WS$, we get that $$S_{kj}(j-\sigma(k))=0.$$ For each $j\ne\sigma(k)$, we have $S_{kj}=0$; so the only nonzero entry in the $k^{\rm th}$ row of $S$ is $S_{k,\sigma(k)}$. In other words, each row of $S$ contains a single nonzero entry, so $S$ is a generalized permutation matrix.

-
Right that makes sense! It's mostly the writing down the equation part I'm having trouble with. So can I say: $SDS^{-1}=W$ for some diagonal $W$ with the same diagonal as $D$ up to a permutation for every $D$, so also for one with all unique diagonal entries. Then when I calculate $SD$ and $WS$ I get equations $(x_j-x_{\sigma(i)})s_{i,j}=0$ for all $i,j$. Then since $x_1-x_{\sigma(i)}$ is only zero for one $i$, the rest of the $s_{i,1}$ must be zero, and so for all j? Or am I making it too complicated? –  dropfruitduo Feb 12 '12 at 20:59
Mostly yes, you need to play a little with the choices of different diagonals. I'll add it to the solution in a few minutes. –  Martin Argerami Feb 12 '12 at 23:45
How about those diagonal matrices with some identical diagonal entries? –  Eric Apr 27 '12 at 14:47
What about them? –  Martin Argerami Apr 28 '12 at 11:44

If $P$ is the permutation matrix corresponding to permutation $\pi$, i.e. $P_{i,\pi(i)} = 1$ for each $i$, and $D$ is a diagonal matrix, then $(PDP^{-1})_{ij} = \sum_k \sum_\ell P_{ik} D_{k\ell} P^{-1}_{\ell j}$. For a term to be nonzero, you need $k = \pi(i)$, $k=\ell$ and $\ell = \pi(j)$, so $\ldots$

-

Let $S \in N(T)$. Now, $\forall D \in T$ we have $SDS^{-1} \in T$. As noted, conjugation preserves the spectrum, and so $D$ and $SDS^{-1}$ have the same diagonal entries up to permutation. This allows us to write $SDS^{-1} = \prod_kP_kDP_k'$, where $P_k, P_k' \in P_{S_n} \leq GL(n)$, the group of permutation matrices. This shows that $N(T) \leq \langle T , P_{S_n}\rangle$. Finally, a simple calculation shows that $\langle T , P_{S_n}\rangle \leq N(T)$.

-

The set of eigenvectors common to all elements of $T$ is that of the nonzero multiples of the standard basis vectors. Any element of $N(T)$ must permute these common basis vectors among each other (if $P\in N(T)$ and $v$ is a common eigenvector of $T$, then so is $P\cdot v$). This means all columns of $P$ must have a single nonzero entry, and of course these entries have to be in distinct rows as well. Hence $N(T)$ is contained in the set of generalised permutation matrices. The reverse inclusion follows from a simple computation to show that permutation matrices normalise $T$ (as of course do elements of $T$ itself). Or show this using the fact that $t\in T$ whenever all standard basis vectors are eigenvectors of $t$ (nearly the converse of the property used at the beginning).

-