Let $\mathbf{A}\in\left\{ 0,1\right\} ^{d\times d}$, and $k(\mathbf{A})$ be the minimal number of $1$s in any column or row in $\mathbf{A}$.


**Question:** What is the minimal $k$ such that, for any $\mathbf{A}$ with
$k\left(\mathbf{A}\right)=k$, we can always find a [permutation matrix](http://mathworld.wolfram.com/PermutationMatrix.html), 
$\mathbf{B\in}\left\{ 0,1\right\} ^{d\times d}$, which $1$s only fall on the $1$s of $\mathbf{A}$, i.e., $\forall i,j:\,B\_{ij}=B\_{ij}A\_{ij}$?



Existence of a permutation matrix on a restricted support
You are asking for a matching in a bipartite graph. The two sides of the graph are the row indices $X=\{1,\dots,d\}$, and the column indices $Y=\{1,\dots,d\}$. The number $k$ is the maximal vertex degree (how many "valid" columns do we have in each row).


$k=\lceil d/2 \rceil$ is the amount needed by an application of [Hall's Marriage Theorem](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem). A bipartite graph on the parts $X,Y$ so that any subset $S \subset X$ has at least $|S|$ neighbors in $Y$ has an $X$-complete matching.


If $k \lt \lceil d/2 \rceil$, then consider the incidence matrix of the complete bipartite graph $K\_{k,d-k}$. Since there are $d-k$ vertices connected to only $k$, there is no matching. 


If $k \ge \lceil d/2 \rceil$, then any nonempty $S \subset X$ has at least $d/2$ neighbors $n(S)$, so if $|S| \gt |n(S)|$ then $|S| \gt d/2$. Since every vertex in $Y$ has degree at least $d/2$, by the pigeonhole principle it must be connected to some vertex in $S$, so $n(S)=Y$. That implies there is a matching. 


