How to find the size of the largest collection of orthogonal rows Given a non-square matrix $M$ over the reals, how can you find the size of the largest collection of orthogonal rows?  
 A: Let $u_1,\ldots, u_n$ be the rows of $M$. Now you calculate $\langle u_i, u_j\rangle$ for all $i,j=1\ldots n$, this value is $0$ if and only if they are orthogonal. While doing this, will be good to have another matrix $\tilde{M}$ (with order $n\times n$) such that $\tilde{M}_{ij}=1$ if $\langle u_i, u_j\rangle=0$ and $\tilde{M}_{ij}=0$ otherwise. With this matrix you can easily find your collection.
Each entry $\tilde{M}_{ij}$ gives you $1$ if the $i$-th and $j$-th rows are orthogonal and $0$ otherwise. Note that this matrix is symmetric with $1$'s on it's diagonal, this means you can construct this matrix fast enough. 
After you have this matrix, you don't need to do more calculations, all you have to do is to check if the entry is $1$ or $0$. Now, you need to make a program to construct the paths of $1$'s in this matrix, such that $\{\tilde{M}_{i_1j_1}, \tilde{M}_{i_2j_2}, \ldots, \tilde{M}_{i_kj_k}$} is a path when $\tilde{M}_{i_rj_s}=1$ for all $r,s=1\ldots k$. This means that you can freely change the indexes and still have $1$ for all the entries. When you finish the first path, you start to construct another one, and when you finish the second one you just compares it's sizes and keep the largest. After that you construct a third one to compare and so on.  
This is easy to implement, which is not equivalent to say that this problem is to be solved in polynomial time. The complexity of a problem has nothing to do with the difficult to create an algorithm (or how complicated it is), complexity has to do with the required computational steps to solve the problem.
