# Complexity of class finding selection of entries in matrix

Suppose I have a matrix with entries either $$x$$ or $$y$$, where the number of rows = number of columns = $$n$$. If I want to select/circle $$n$$ entries such that for each row, only exactly one is circled, for each column, also exactly one is circled, and such that all entries circled are only $$x$$ (if such a circling of entries exists), what complexity class does this belong to? Thanks!

Let $$U$$ be the set of rows in the given matrix and $$V$$ the set of columns. For each $$x$$ at row $$i$$ and column $$j$$, add an edge between row $$i$$ and column $$j$$. You will have an (unweighted) bipartite graph $$G=(U,V, E)$$. The problem is to find a perfect matching, which is basically the same as find the maximum matching of $$G$$.
There are various algorithms that compute the maximum cardinality matching. For example, The Hopcroft–Karp algorithm runs in $$O(\max(|E|\sqrt {|V|}, |V|^2)$$.
So, we can say that the complexity class of the problem in the question is in $$O(n^{2.5})$$ since $$|E|\le n^2$$ and $$|V|= 2n$$.