Proof permutation matrix

linear algebrapermutation-matrices

For every permutation $\sigma \in S_n$ we define a $n \times n$ matrix $$P_\sigma:=(\delta_i,\sigma_j)_{1\le i,j\le n}$$

Show that the matrix $P_\sigma$ is a permutation matrix and for every permutation matrix $P$ there is only one permutation $\sigma \in S_n$ such that $P=P_\sigma$.

I don't really get the notation here, could someone quickly clear that up.

I mean i know that $\sigma$ is bijective meaning $\sigma: \{1,2,3,4,…..,n\} \rightarrow \{\sigma_1,\sigma_2,\sigma_3,\sigma_4,…..,\sigma_n\}$ But in this case for $P_\sigma$ to be a permutation matrix, don't i have to use Kronecker Delta to to define if $\delta_i=\sigma_j$ then we have 1, otherwise 0, for
$P_\sigma$ to be a permutation matrix…But from the question i get the feeling i dont need to do this or rather i'm not allowed to do this. So i thought maybe that notation means something else than i thought.

Best Answer

Notation $$(\delta_i,\sigma_j)$$ should be interpreted as the value of Dirac $\delta_i$ acting on $\sigma_j$ (see for example here), i.e.,

$$\delta_i(\sigma_j)=\begin{cases}1 & \text{if} \ \sigma_j=i \iff \sigma(j)=i\\0 & \text{otherwise}\end{cases}$$

giving indeed exactly one "$1$" on every line.

For your second part: on inspection of a permutation matrix, which is known to have one "1" per line and per column (it is their definition), on each line "i", there is a unique "one" situated on a certain column $j$ determines the image $\sigma(j)=i$. When all lines have been processed, $\sigma$ is fully determined. But $\sigma$ has to be proven injective. This is where the other unicity intervenes: no chance that $\sigma(j_1)=\sigma(j_2)$ for $j_1 \ne j_2$ because there is a unique "one" per column.

The result is indeed the classical permutation matrix associated to $\sigma$...

Remark: notation $(u,v)$ is indeed puzzling ; it is usually used for dot products, but sometimes as well for the "action" of the first argument onto the second: $(f,x):=f(x)$, mainly in the context of duality (like in the reference I gave above).

Related Question