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, $\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}$?
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. 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.
