Summary: Let \(\Lambda_n^k\) be the set of all \(n \times n\) binary matrices with exactly \(k\) units in each row and each column, \(1 \leq k \leq n\). A matrix \(A \in \Lambda_n^k\) will be called primitive, if there is no \(l \times l\) submatrix of \(A\) that belongs to the set \(\Lambda_l^k\), \(k \leq l < n\). The article describes a polynomial algorithm, which works in time \(O(n^2)\) for verifying whether a \(\Lambda_n^k\)-matrix is primitive. The work applies this algorithm for finding all primitive \(\Lambda_n^k\)-matrices which rows and columns are in lexicographically nondecreasing order (semi-canonical binary matrices) for some integers \(n\) and \(k\).