Every matrix can be written as a sum of unitary matrices?

The reference to the MathOverflow question is a good one. If $A$ is a complex matrix, you can normalize so that $\|A\| \le 1$. Then $$ A = B + iC $$ where $B$, $C$ are selfadjoint and given by $$ B = \frac{1}{2}(A+A^{\star}),\;\;\; C=\frac{1}{2i}(A-A^{\star}). $$ These selfadjoint operators also satisfy $\|B\| \le 1$ and $\|C\|\le 1$, which means that their eigenvalues--which must be real--are in $[-1,1]$. Then you can decompose $B$ and $C$ as $$ B = \frac{1}{2}(U_{B}+V_{B}),\;\;\; C=\frac{1}{2}(U_{C}+V_{C}) $$ where $U_{B}, V_{B}, U_{C}, V_{C}$ are unitary and given by $$ U_{B} = B + i\sqrt{I-B^2},\;\; V_{B}=B-i\sqrt{I-B^2} \\ U_{C} = C + i\sqrt{I-C^2},\;\; V_{C}=C-i\sqrt{I-C^2} $$ This makes sense becaue $I-B^2$ and $I-C^2$ are selfadjoint with their eigenvalues in $[0,1]$; so the square roots are defined that also have eigenvalues in $[0,1]$. You can check that $$ U_{B}U_{B}^{\star}= U_{B}^{\star}U_{B} = (B-i\sqrt{I-B^2})(B+i\sqrt{I-B^2})=B^2+(I-B^2)=I. $$ Then $\frac{1}{2}(U_{B}+V_{B})=B$, $\frac{1}{2}(U_{C}+V_{C})=C$ and $A=B+iC$ is a linear combination of unitary matrices.

It is known that every complex square matrix $A$ can be written as a linear combination of at most two unitary matrices. First, by scaling, you may assume that $\|A\|\le1$. Then, by singular value decomposition, you may also assume that $$ A=\operatorname{diag}(s_1,\ldots,s_n) $$ where the singular values $s_j$s are real nonnegative and bounded above by $1$. Now, as $s_j=\frac12(z_j+\bar{z}_j)$, where $z_j=s_j+i\sqrt{1-s_j^2}$ has unit modulus, it follows that $A$ is the average of two unitary matrices.

If I remember correctly, there was also an open conjecture that the least possible number $k(n)$ such that every real $n\times n$ matrix can be written as a linear combination of at most $k(n)$ real orthogonal matrices is equal to $4$. It has been shown that $k(n)\le 4$. See proposition 1 in Chi-Kwong Li and Edward Poon, Additive Decomposition of Real Matrices, Linear and Multilinear Algebra, 50(4):321-326, 2002.

I do not see an elementary linear algebra proof right now, but an answer is given at this MO-question, namely that in a $C^*$-algebra, any operator is the linear combination of four unitary operators. The algebra $M(n, \mathbb{C})$ of $n × n$ matrices over $\mathbb{C}$ becomes a $C^*$-algebra if we consider matrices as operators on the Euclidean space $\mathbb{C}^n$, and use the operator norm $||.||$ on matrices.