That solution Roland suggested is kinda crossing the line to me for many reasons... Anyway, I feel like the professor might get upset when he sees the published date on arXiv. He might think someone beat him to it because the lazy grad student was slacking off, not writing up the result quickly?

This is kind of irrelevant now that we know OP meant avoiding constant submatrices of adjacent rows and columns, but you can get a $3 \times 5$ matrix A avoiding constant $2 \times 2$ (general) submatrices by choosing $(1,0,0,0,1)$ as the third row; this choice is ok because your argument doesn't require the third row to have three $1$'s.

Totally unrelated to your question, but you've got one too many http's in your linked url. It should read: math.stackexchange.com/questions/233602/generalized-traces