I'm stuck in this problem.
Prove the set $P$ of $n×n$ permutation matrices spans a subspace of dimension $(n−1)^2+1$
[Math] Set of permutation matrices
linear algebramatricespermutations
linear algebramatricespermutations
I'm stuck in this problem.
Prove the set $P$ of $n×n$ permutation matrices spans a subspace of dimension $(n−1)^2+1$
Best Answer
Remark that if $M\in \mathit{Span}(P)$, then there is $\lambda$ such that for all line or column $x$ of $M$, the sum of elements of $x$ is $\lambda$.
Let $V$ be the space of matrices verifying this condition, we have $\mathit{Span}(P)\subseteq V$, and every $M\in V$ is uniquely defined by the $M(i,j)$ with $0\leq i,j\leq n-1$, together with the sum $\lambda$. It implies that $\mathrm{dim}(\mathit{Span}(P))\leq\mathrm{dim}(V)= (n-1)^2+1$.
For the other direction, it suffices to show that $\mathrm{dim}(\mathit{Span}(P))\geq (n-1)^2+1$.
For this, you can verify that the following set of matrices are independent: $\mathit{Id}$, $\tau_{1,x}$, $(1,x,y)$, where $1\neq x\neq y\neq 1$. The last argument is from here.