2. ## Matrices

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

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

Then $\displaystyle \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 $\displaystyle i, (1\le i\le n), y_i$ is formed when the elements of row $\displaystyle i$ of matrix $\displaystyle P$ are combined (by multiplication and addition) with the elements of $\displaystyle x$. In other words:

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

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

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

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