Is there a simple description of the the convex hull of all the pairs of $n$ by $n$ matrices $(A,B)$ such that $$AA^t+BB^t=A^tA+B^tB=I$$ This is a convex set in dimension $2n^2$, and I am hoping for a simple characterization of the pairs of matrices that belong to it.
It is an interesting question. Where does it come from? In the case $n=1$ the pairs are $\left [\cos u,\sin u\right]$ with convex hull the unit disk. I don't have anything that explicit to say about larger $n.$ In fact I mostly have more questions disguised as comments One can also look at stronger conditions, find the convex hull in those cases and then consider the convex hull of these convex hulls. The case that $A$ and $B$ are both diagonal matrices is pretty understandable or even the case that each is a generalized permutation matrix. On could also look at the case that $B$ (or $A$) is the zero matrix. Weaker conditions will give an upper bound for the convex hull. Relaxing the conditions to merely $AA^t$ and $BB^t$ each have diagonal entries no larger that $1$ means that each row is on or inside $S_n$, the unit sphere in $\mathbb{R}^n.$ what does the convex hull look like in that case? What if we have that result for both rows and columns? Using the fact that $AAt+BB^t$ has diagonal entries $1$ means that for each $i$ there is $\theta_i$ with the row $i$ of $A$ on $\cos(\theta_i)S_n$ and row $i$ of $B$ on $\sin(\theta_i)S_n$. The same goes for columns. So in the case $n=2$ solutions will have the form $$\left( \left[ \begin {array}{cc} \sin \left( w \right) \sin \left( u \right) &\cos \left( w \right) \cos \left( t \right) \\\ \cos \left( w \right) \cos \left( s \right) &\sin \left( w \right) \sin \left( v \right) \end {array} \right] , \left[ \begin {array}{cc} \sin \left( w \right) \cos \left( u \right) &\cos \left( w \right) \sin \left( t \right) \\\ \cos \left( w \right) \sin \left( s \right) &\sin \left( w \right) \cos \left( v \right) \end {array} \right] \right) $$ This leaves the off diagonal elements which are $\sin(w)\cos(w)(sin(u+s)+sin(t+v))$ and $\sin(w)\cos(w)( sin(u+t)+sin(s+v))$. In the case that $\sin(w)\cos(w)=0$, $A,B$ are diagonal or antidiagonal. Otherwise $t+v=2j\pius$ for $j=1,2$ or $3$. Or else $t+v=u+s+(2j1)\pi$ for $1 \le j \le 2.$ This is seven cases with another seven for $s+v$. Putting all this together gives (if my short program in accurate) $43$ additional cases. Many of these are negations or transposes of other solutions. Most have three free parameters but some are impossible and some, such as the case $t+v=6\pius, s+v=6\pi+ut$ yield $$ \left(\left[ \begin{array}{cc} \sin \left( w \right) \sin \left( u \right) &\cos \left( w \right) \cos \left( t \right) \\\ \cos \left( w \right) \cos \left( t+v+u \right) & \sin \left( w \right) \sin \left( v \right) \end {array} \right] , \left[\begin {array}{cc} \sin \left( w \right) \cos \left( u \right) &\cos \left( w \right) \sin \left( t \right) \\\ \cos \left( w \right) \sin \left( t+v+u \right) &\sin \left( w \right) \cos \left( v \right) \end{array}\right] \right) $$ 


$\max(\A^*A+B^*B\,\A A^*+B B^*\)\leq 1$
? Or do you already know that it is smaller? – Mikael de la Salle Oct 1 '12 at 11:36$\max(\A^*A+B^*B\,\A A^*+B B^*\)\leq 1$
? – Mikael de la Salle Oct 1 '12 at 11:39