Well, in practice you start with a given switch count, not with a given pin count. The switch count seldom is a square number (49, 64, 81, 100, 121 or 144), so you often can choose between several matrix layouts which have the same pin count as the square matrix for your number of keys.
The point I wanted to make is that there are a number of factors involved with that matrix choice and that you can make your life easier by making a clever choice if you have a choice (and you usually have). This is about simplicity, not perfectionism.
flabbergast wrote: The debouncing delays effectively kill any advantage you get by wiring smartly

There is a common misconception about the debouncing delay: Usually, people wait
before they accept the state change. That's wrong. You only need to veto
after you accepted the state change. (Unless you have noise on your lines that does not originate from bouncing, but that would be another issue.)
If your switch has been "off" for a while, already the first change to "on" indicates the keypress - you don't need to wait until it has become stable, you only must avoid mistaking the bounce back to "off" as a release of the key. By the same token, when your switch has been "on", it is the first drop to "off" that indicates that the user is releasing the key, you only must avoid confusing the bounce back to "on" with a new press. So you simply ignore the switch for a while after you registered a state change. Again, this is simplicity, not perfectionism.