Putnam 2014, Problem B-3

Let $A$ be an $m \times n$ matrix with rational entries. Suppose that there are at least $m + n$ distinct prime numbers among the absolute values of the entries of $A$. Show that the rank of $A$ is at least $2$.

Solution:
First solution: Assume \(A\) has rank at most 1, so \(A_{ij} = a_i b_j\) for rational \(a_i, b_j\). Then \(|a_i b_j|\) is prime iff \(c(a_i) + c(b_j)\) has one entry 1 and others 0, where \(c(q) = (c_1, c_2, \dots)\) is the prime factorization of \(q\). The condition that \(m + n\) distinct primes appear implies the vector space \(\left\{ \sum_i x_i c(a_i) + \sum_j y_j c(b_j) : x_i, y_j \in \mathbb{R}, \sum_i x_i = \sum_j y_j \right\}\) has dimension \(m + n\), but it has dimension at most \(m + n - 1\), a contradiction.  
Second solution: Draw a bipartite graph with rows and columns of \(A\) as vertices, and an edge if the entry is prime. A rank-1 matrix implies the graph has a cycle. Since the graph is bipartite, the cycle has length \(2k \geq 4\). Let the cycle be row 1, column 1, row 2, column 2, ..., row \(k\), column \(k\). Then \(|A_{11}| = p_1, \dots, |A_{kk}| = p_k\) are distinct primes. Since \(A\) has rank 1, the \(2 \times 2\) minor \(A_{11} A_{ij} - A_{1j} A_{i1} = 0\) for all \(i,j\). Let \(r_i = |A_{i1}|\) and \(c_j = |A_{1j}/A_{11}|\), so \(p_1 \cdots p_k = (r_1 c_1) \cdots (r_k c_k) = (r_1 c_1 \cdots r_k c_k)^2\), contradicting unique prime factorization.