By "solution", I mean a PseudoInverse. By "exact", I mean a formula, not a fit (such as SVD) or a decomposition.
When working on a probability problem like this, it's important to define the problem precisely otherwise you run into a more complicated version of bertrand's paradox http://en.wikipedia.org/wiki/Bertrandparadox(probability).
There are many different ways to described the space of all rectangular matrices which might be intuitively seen as "level" or "equal". These might give different results. In short, you have to choose an algorithm for generating a "random matrix" of the type you're looking for, otherwise the question won't make sense.
Of course, once you have such an algorithm for generating a "random matrix" you can run a short monte carlo experiment to get the number numerically. Questions similar to the one you've asked here are, from what little I've read on the subject, asked in random matrix theory.
Thank you. You are giving me too much credit in terms of sophistication. Assume that question was asked in a first year Linear Algebra course. The student is asking for a very simple example of a rectangular matrix that can be solved by a trick as simple as rotating the matrix followed by multiplication and division of nonzero elements to obtain the pseudoinverse. They don't want to see an answer that involves decomposition methods or SVD. Think of it as a "Penrose trick".
I could ask this in a specific manner. Would anyone be surprised that a matrix of this form has a very simple method for obtaining the pseudoinverse?
alpha = 4; word = 3; (* for example*)
Flatten[Tuples[Reverse[IdentityMatrix[alpha]], word]], (alpha*word)]]
I'm back to SVD and SVD short cuts, possibly because of redundancy.