How to generate a rectangular matrix that has no left/right inverse?

Question

Is it possible to generate non-invertible rectangular matrices? If so, how we can prove it? And is there any way to generate randomly such matrices in MATLAB (with preferably uniform distribution)?

Answer 1

A wide (resp. tall) matrix $A$ has no right (resp. left) inverses if and only if it has deficient row (resp. column) rank, i.e. if and only if the rows (resp. columns) of $A$ are linearly dependent. Owing to the dependency between rows/columns, what you mean by "uniform distribution" is unclear.

At any rate, here are some methods that you may consider. Without loss of generality, suppose $A$ is an $m\times n$ wide matrix (so that $m<n$). Presumably, the entries of $A$ are real numbers.

1. Generate a random integer $k$ between $0$ and $m-1$. If $k=0$, set $A=0$. Otherwise, generate $k$ random row vectors $\mathbf{r}_1,\ldots,\mathbf{r}_k$, each of length $n$. For $i=1,2,\ldots,m$, generate a probability vector $(p_1,p_2,\ldots,p_k)$ (i.e. $0\le p_i\le 1$ and $\sum_ip_i=1$). Set the $i$-th row of $A$ to $\sum_i p_i\mathbf{r}_i$.
2. Generate a random integer $k$ between $0$ and $m-1$. If $k=0$, set $A=0$. Otherwise, generate $k$ random column vectors $\mathbf{c}_1,\ldots,\mathbf{c}_k$, each of length $m$. For $j=1,2,\ldots,n$, generate a probability vector $(p_1,p_2,\ldots,p_k)$. Set the $j$-th column of $A$ to $\sum_j p_j\mathbf{c}_j$.
3. Generate a random integer $k$ between $0$ and $m-1$. Generate $k$ random nonnegative real numbers $\sigma_1,\ldots,\sigma_k$ within some range. Generate an $m\times m$ real orthogonal matrix $U$ and an $n\times n$ real orthogonal matrix $V$ (see Wikipedia for an algorithm). Then set $$ A=U\left[\operatorname{diag}(\sigma_1,\ldots,\sigma_k,0,\ldots,0),\ 0_{m\times(n-m)}\right]V. $$