Let $A$ be a matrix whose entries are either 1 or 0.The number of entries which equals 1 for every row of $A$ is exactly $k$ and the number of 1 for every column is no larger than $k$.Prove that there exists $P_1,P_2,\cdots,P_k$,such that $A=\sum\limits_{i=1}^kP_i$,and for each $P_i$,the number of 1 for every row is 1,the number of 1 for every column is no larger than 1.
Ideas:This can also be seen as a matching problem in graph theory.If we take every row (X) and every column (Y) as a vertex,and they are connected iff the entry is 1.This is a bigragh.If we induct on k,for $k'\leq k-1$ it holds,then for $A$,we need to find the $P_k$,such that $A-P_k$ is fit for the induction.For all the vertex $Y'$ in $Y$ whose degree equals $k$,then we need a match between $X$ and $Y$,such that every $X$ and every $Y'$ is matched.
Any such matrix has at least as many columns as rows (by counting the total number of ones in two different ways; by rows, and by columns). If it is a square matrix, then (by the same technique) every column has exactly $k$ ones. If it is not a square matrix, it can be extended to one by adjoining enough rows to make it square, putting $k$ ones in the rows you have added, putting those ones where they can go without causing any column to overflow (that is, to have more than $k$ ones). So, either way, we get a square matrix $B$ of zeros and ones, with exactly $k$ ones in each row and in each column.
Now we can apply Hall's Theorem to find a permutation matrix $P_1$ such that $P_1$ has ones only in places where $B$ has ones. Then $B-P_1$ is a square matrix of zeros and ones with exactly $k-1$ ones in each row and in each column. Iterate the procedure $k$ times to get $B=\sum_1^kP_i$. Then delete the additional rows from $B$ and from each $P_i$ to get $A=\sum_1^kP'_i$ where each $P'_i$ has a single one in each row, and at most one one in each column.