How to find a perfect matching with this constraint?
We consider three different cases: $\alpha &lt; 1$, $\alpha = 1$, and $\alpha &gt; 1$. 

Suppose first that $\alpha &lt; 1$. Arrange the $n^2$ elements in the matrix in non-increasing order: $x_1,x_2,\ldots$. Note that $x_1,\ldots,x_n$ must belong to the diagonal, and moreover $\alpha x_n \geq x_{n+1}$. Hence the instance is solvable iff $\alpha x_n \geq x_{n+1}$ and $x_1,\ldots,x_n$ belong to different rows and columns.

The case $\alpha = 1$ is very similar. Let $x_1 = x_2 = \cdots = x_m &gt; x_{m+1}$. If $m = n$ then we are back to the previous case. If $m &lt; n$, then $x_1,\ldots,x_m$ must belong to the diagonal. We find out whether it is possible, fix this part of the permutation, and iterate (details left to you). The most interesting case is when $m &gt; n$. In that case, we use a bipartite perfect matching algorithm to find out whether $n$ of these $m$ elements can be put on the diagonal.

The case $\alpha &gt; 1$ is slightly more complicated. Let $A$ be the list of elements larger than $\alpha x_n$. All of these elements (if any) must belong to the diagonal in any solution, since the diagonal always contains an element at least as small as $x_n$. If $A \neq \emptyset$, we first check that they can be put in the diagonal, fix this part of the permutation, and iterate. If $A = \emptyset$, then we check whether the first $n$ elements can be put on the diagonal. If so, we have found a solution. Otherwise, we know that the solution must contain an element at least as small as $x_{n+1}$ on the diagonal, and we let $A$ be the list of these elements. If $A \neq \emptyset$, we do what we did before. Otherwise, we use a bipartite perfect matching algorithm to try and fit $x_1,\ldots,x_{n+1}$ on the diagonal (deleting first elements conflicting with the current partial permutation). If so, we have found a solution. Otherwise, we continue with $x_{n+2}$. Eventually we will have made a conclusion, since when reaching $x_{n^2}$ the answer is positive.