Rectangular Orthogonal Matrix Consider a overcomplete matrix $D$ of dimension $m\times n$ where $n>m$.
I want to know under what conditions i can say $D$ has orthogonal columns or rows. More specifically when $D$ will be close to a orthogonal matrix.
My algorithm computes $D$. Now $D^TD$ is giving me a matrix close to $I$ whose diagonal is 1 and off diagonal elements are very close to zero say $10^{-20}$. 
But as per some literature if $D$ has orthogonal rows then $DD^T$ should give me $I$ identity matrix for $n>m$.
Similarly $D$ has orthogonal columns if $D^TD$ gives me $I$ identity matrix for $n<m$.
Can someone help me understanding the properties of my generated matrix $D$? 
 A: Numerical linear algebra studies the use of floating point computations for linear algebra. Now one concept there is the machine epsilon, a smallest representible number for the particular computer you're on. Numbers of the same order as $\epsilon_{mach}$ are often considered to be zero.
Algorithms in numerical linear algebra often make reference to $\epsilon_{mach}$, as well as to the particular problem at hand. For example, the rank of a matrix is computed as the number of singular values (look up SVD) greater than a judiciously chosen constant close to $\epsilon_{mach}$.
One way to think about it is: imagine your algorithm operating in a perfect world with infinite bits of precision for each number. Now turn down the number of bits and watch the answers of your algorithm. Some of the previous zeros are now going to be (erroneously) rounded up. $\epsilon_{mach}$ is the smallest number they can be rounded up to, so it's kind of the natural unit. For 32 bit floating point numbers $\epsilon_{mach}$ is $10^{-22}$.
All this is a long-winded way of saying: your algorithm is probably computing the correct answer, as close to correct as you can be given finite precision intermediate computations.
Read Trefethen and Bau's Numerical Linear Algebra for more, or wikipedia conditioning, stability, floating point arithmetic, and machine epsilon.
