  Linear programming on the Stiefel manifold (LPS) is studied for the first
time. It aims at minimizing a linear objective function over the set of all
$p$-tuples of orthonormal vectors in ${\mathbb R}^n$ satisfying $k$ additional
linear constraints. Despite the classical polynomial-time solvable case $k=0$,
general (LPS) is NP-hard. According to the Shapiro-Barvinok-Pataki theorem,
(LPS) admits an exact semidefinite programming (SDP) relaxation when
$p(p+1)/2\le n-k$, which is tight when $p=1$. Surprisingly, we can greatly
strengthen this sufficient exactness condition to $p\le n-k$, which covers the
classical case $p\le n$ and $k=0$. Regarding (LPS) as a smooth nonlinear
programming problem, we reveal a nice property that under the linear
independence constraint qualification, the standard first- and second-order
{\it local} necessary optimality conditions are sufficient for {\it global}
optimality when $p+1\le n-k$.
