Matrices question

Hello champrock

Quote:

Originally Posted by champrock

http://img232.imageshack.us/img232/7...0952623pmy.png

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\{<br /> \begin{array}{l l}<br /> 0 & \quad k \ne j\\<br /> 1 & \quad k = j\\<br /> \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$ .

Grandad