Let Q_n be a random n by n matrix with entries in {0,1} whose rows are independent vectors of exactly n/2 zero components. We show that the probability that Q_n is singular is exponentially small, which is optimal up to a multiplicative factor.