Consider an n times n matrix A such that each entry is eithe

Consider an n times n matrix A such that each entry is either 0 or 1. Prove that if A is invertible then the number of ones is at least n and not more than n^2 - n + 1.

Solution

If the matrix A is invertible, then, its determinant 0. It implies that all its rows are non-zero, for ,otherwise, det (A) would be 0 and A will not be invertible. Thus A must have atleast n non-zero rows.so that the number of ones is atleast n. Further, since A is invertible, its rows are linearly independent. Thus, only one row of A can have all ones. The remaining (n-1) rows can have maximum of (n-1) ones each. Thus, the maximum number of ones in A = n + (n-1)(n-1) = n + n² -2n +1 = n² –n + 1.