2. ## Matrices

Hello champrock
Originally Posted by champrock
The answer is (c): every row and every column of $P$ contains just one $1$, and $(n-1)$ zeros. Let me try and explain why.

Suppose the elements of $P$ are $p_{i,j}$. In other words the element in row $i$, column $j$ is $p_{i,j}$. Suppose also that the elements of $x$ are $x_1, x_2, \dots, x_n$, and the elements of $y$ are $y_1, y_2, \dots, y_n$

Then $\begin{pmatrix}y_1\\y_2\\ \dots\\y_n\end{pmatrix} = \begin{pmatrix}p_{1,1}&p_{1,2}&\dots& p_{1,n}\\p_{2,1}&\dots&\dots &\dots \\ \dots&\dots &\dots&\dots \\p_{n,1}&\dots&\dots& p_{n,n}\end{pmatrix}\begin{pmatrix}x_1\\x_2\\ \dots\\x_n\end{pmatrix}$

Now for each $i, (1\le i\le n), y_i$ is formed when the elements of row $i$ of matrix $P$ are combined (by multiplication and addition) with the elements of $x$. In other words:

$y_i = \sum_{k=1}^np_{i, k}x_k$

And $y$'s elements are a re-arrangement of $x$'s elements. So for each $i, y_i = x_j$ for some $j, 1 \le j\le n$. Therefore, from the above equation:

$p_{i,k} = \left\{
\begin{array}{l l}
0 & \quad k \ne j\\
1 & \quad k = j\\
\end{array} \right.$

So each row of $P$ contains a single $1$, and $(n-1)$ zeros. Moreover, each $y_i$ is equal to a different $x_j$, so no column of $P$ contains more than a single $1$. So $P$ is bistochastic, with elements $0$ and $1$.