Permutation Matrix P and Diagonal Entries of PA I am trying to the problem below and I have no idea how to begin. I want to show that:
If $A\in\mathbb{R}^{n\times n}$ is nonsingular, then there exist a permutation matrix $P$ such that $PA$ has nonzero diagonal entries.
I know what permutation matrices are but how to connect with this, I have no clue. Can someone please help me out here.
 A: Here's an outline . . .

Suppose $A$ is non-singular. Then $\det(A)$ is nonzero.

But $\det(A)$ is the sum of signed products of generalized diagonals, hence at least one generalized diagonal, $D$ say, must have all nonzero entries.

Let $Q$ be the permutation matrix corresponding to $D$, and let $P = Q^{-1}$.

Since $PQ = I_n$, it follows that entries of the diagonal of $PA$ are some permutation of the entries of $D$, hence are all nonzero.
A: Similar questions have been asked, e.g. If matrix $A$ is invertible, then there is a permutation of its rows leaving no-zeros on the diagonal, where the answer is similar to quasi's.
A simple example, however, may help new comers.  Consider, for instance,
$$A=\left[\begin{array}{cc}a_{11} & a_{12} \\a_{21} & a_{22}\end{array}\right].$$
$A$ is nonsingular, so $\det(A)\ne 0.$  Since $\det(A)=a_{11}a_{22}-a_{12}a_{21}$, one of the product must be nonzero.  If $a_{11}a_{22}\ne 0$, we're done.  Otherwise, $a_{12}a_{21}$ must be nonzero, and we can permute $a_{12}$ and $a_{21}$ into the diagonal.  The same idea applies to larger matrices.
