Linear Algebra – The Transpose of a Permutation Matrix is Its Inverse

abstract-algebralinear algebramatricespermutation-matricespermutations

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post.

This problem is from assignment 4.

Prove that the transpose of a permutation matrix $P$ is its inverse.

A permutation matrix $P$ has a single 1 in each row and a single 1 in each column, all other entries being 0. So column $j$ has a single 1 at position $e_{i_jj}$. $P$ acts by moving row $j$ to row $i_j$ for each column $j$. Taking the transpose of $P$ moves each 1 entry from $e_{i_jj}$ to $e_{ji_j}$. Then $P^t$ acts by moving row $i_j$ to row $j$ for each row $i_j$. Since this is the inverse operation, $P^t=P^{-1}$.

Again, I welcome any critique of my reasoning and/or my style as well as alternative solutions to the problem.

Thanks.

Best Answer

A direct computation is also fine: $$(PP^T)_{ij} = \sum_{k=1}^n P_{ik} P^T_{kj} = \sum_{k=1}^n P_{ik} P_{jk}$$ but $P_{ik}$ is usually 0, and so $P_{ik} P_{jk}$ is usually 0. The only time $P_{ik}$ is nonzero is when it is 1, but then there are no other $i' \neq i$ such that $P_{i'k}$ is nonzero ($i$ is the only row with a 1 in column $k$). In other words, $$\sum_{k=1}^n P_{ik} P_{jk} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{otherwise} \end{cases}$$ and this is exactly the formula for the entries of the identity matrix, so $$PP^T = I$$

Related Solutions

Abstract Algebra – $f(x)= {}^tx^{-1}$ as an Automorphism of GL$_n(\mathbb{R})$

The math all looks fine. Here are some style critiques (bear in mind that style critiques are somewhat subjective.)

Although the order does not matter, I bristle at seeing the $t$ and $-1$ on either side of a matrix without an indication of which is done first. In the lectures, presumably this exercise appears after some discussion where it is proved that the order is immaterial, but divorced from such a context, it looks a little weird. (If only because the proof that the order is immaterial is so similar to the proof that $f$ is multiplicative--- both are algebraic calculations involving a delicate balance of transposing and inversing, and how these operations individually treat products.)
I would write "So $f$ is invertible, and in fact $f^{-1} = f$" rather than "So $f^{-1} = f$." (General principle: if $f$ has not yet been explicitly announced as invertible, do not write $f^{-1}$.) If you don't buy that general principle, I would still say: at this stage in the argument, the very existence of $f^{-1}$ has just been established, and this deserves more notice than the fact that $f^{-1} = f$, because it is the existence of the inverse that really establishes that $f$ is an automorphism, and not so much the specific fact that $f^{-1}$ happens to be $f$.
Depending on how "automorphism" has been defined--- it may have been defined to be a homomorphism that has an inverse in the sense that you just established $f$ did--- it may not be necessary to detour through bijectivity to get to the fact that $f$ is an automorphism. In any case, "Since $f$ has an inverse for all $A \in \operatorname{GL}_n(\mathbb{R})$" should at least be replaced with just "Since $f$ has an inverse", because the "for all $A \in \operatorname{GL}_n(\mathbb{R})$" is meaningless here. (The map $f$ either has an inverse or does not; "has an inverse" is not a parametrized statement that depends on a matrix $A$.)
I would re-order the discussion in the last paragraph a little bit. The issue for me is the distance between restatements of assumptions and where they are used. "There is some $B \in \operatorname{GL}_n(\mathbb{R})$ with $f(A) = BAB^{-1}$" is where the assumption that $f$ is an inner automorphism is being used, but as currently written, this assertion is introduced by the statement "Since $A$ is in the center of $\operatorname{GL}_n(\mathbb{R})$". This does not explain why there is that $B$, but rather why the calculational step following that assertion (namely the equality $BAB^{-1} = BB^{-1}A$) is valid.
In "Let $A = \lambda I_n$" you are implicitly introducing the number $\lambda$, but not telling the reader anything else about it. On finishing this sentence, a reader may be unsure whether (a) you are intending to choose a specific value of $\lambda$ later, or (b) you intend to do something for an arbitrary value of $\lambda$, or (c) you have already fixed a value of $\lambda$ somewhere, and the reader accidentally skipped over it.

The item (c) is the most important one to be mindful of in situations like this--- if not when writing individual exercise solutions, in longer-form mathematical writing. Wherever possible, when introducing a new symbol, make clear that you are introducing it, so the reader doesn't re-scan what they've just read looking for something they missed.

You could, for example, say "Fix any nonzero number $\lambda$ and consider $A = \lambda I_n$. From the definition of $f$ we have $f(A) = \cdots = \lambda^{-1} I_n$, and in particular if we choose $\lambda \neq \pm 1$ we see that $f(A) \neq A$. On the other hand, if $f$ were inner we would have [...] So $f$ is not inner." [Note that $\lambda^{-1} = \lambda$ holds for $\lambda = -1$ also; I guess this is a tiny math error in the original.]

Alternatively, you could avoid the symbol $\lambda$ entirely and just do the calculation for one particular value of $\lambda$, e.g. $2$. This is where people fall into two camps. Some would say that it is bad to randomly introduce $2 I_n$ to the discussion without any indication of where the choice "came from", and that the discussion with general $\lambda$ followed by a specialization to $\lambda \neq \pm 1$ leaves the reader with more understanding. Others would say that as the goal is only to show by example that $f$ is not inner, then it complicates things to introduce a parameter into the discussion when one can give just a single example.

Abstract Algebra – Fibres of a Map Form a Partition of the Domain

As ineff said, your solution is fine, and ineff has given you the other natural solution. Since you’re studying on your own, I just want to emphasize that if $G$ is a set, equivalence relations on $G$, partitions of $G$, and functions with domain $G$ are three ways of looking at essentially the same thing.

You’ve already seen that if $R$ is an equivalence relation on $G$, $\mathscr{P}(R)=\{[x]_R:x\in G\}$ is a partition of $G$ (where $[x]_R$ is the $R$-equivalence class of $x$), and if $\mathscr{Q}$ is a partition of $G$, then the relation $E(\mathscr{Q})$ defined by $$x\;E(\mathscr{Q})\;y \iff \exists Q\in\mathscr{Q} \big(x,y\in Q\big)$$ is an equivalence relation on $G$. Moreover, $E\big(\mathscr{P}(R)\big)=R$ for any equivalence relation $R$ on $G$, and $\mathscr{P}\big(E(\mathscr{Q})\big)=\mathscr{Q}$ for any partition $\mathscr{Q}$ of $G$. In other words, there’s a natural bijection between equivalence relations on $G$ and partitions of $G$ given by $R\mapsto\mathscr{P}(R),\mathscr{Q}\mapsto E(\mathscr{Q})$: every equivalence relation determines a partition, which in turn determines the original equivalence relation.

In this exercise you’ve shown that if $f$ is any function with domain $G$, the fibres of $f$ form a partition of $G$, say $\mathscr{P}(f)$. This correspondence also goes both ways. Suppose that $\mathscr{Q}$ is a partition of $G$. Define $g_\mathscr{Q}:G\to\mathscr{Q}$ by letting $g_\mathscr{Q}(x)$ be the unique member of $\mathscr{Q}$ containing $x$; clearly $g_\mathscr{Q}$ is a function with domain $G$, and it’s very easy to check that

$\qquad(1)\qquad\mathscr{P}(g_\mathscr{Q})=\mathscr{Q}$ for any partition $\mathscr{Q}$ of $G$, and
$\qquad(2)\qquad g_{\mathscr{P}(f)}=f$ for any function $f$ with domain $G$.

That is, we have a natural bijection between partitions of $G$ and functions with domain $G$ given by $\mathscr{Q}\mapsto g_\mathscr{Q},f\mapsto\mathscr{P}(f)$: every partition determines a function that in turn determines the original partition.

And of course these give rise to a natural bijection between equivalence relations on $G$ and functions with domain $G$.

You’ll be using all three points of view when you study quotient groups.

Best Answer

Related Solutions

Abstract Algebra – $f(x)= {}^tx^{-1}$ as an Automorphism of GL$_n(\mathbb{R})$

Abstract Algebra – Fibres of a Map Form a Partition of the Domain

Related Question