  Determining the total variation mixing time of Kac's random walk on the
special orthogonal group $\mathrm{SO}(n)$ has been a long-standing open
problem. In this paper, we construct a novel non-Markovian coupling for
bounding this mixing time. The analysis of our coupling entails controlling the
smallest singular value of a certain random matrix with highly dependent
entries. The dependence of the entries in our matrix makes it not-amenable to
existing techniques in random matrix theory. To circumvent this difficulty, we
extend some recent bounds on the smallest singular values of matrices with
independent entries to our setting. These bounds imply that the mixing time of
Kac's walk on the group $\mathrm{SO}(n)$ is between $C_{1} n^{2}$ and $C_{2}
n^{4} \log(n)$ for some explicit constants $0 < C_{1}, C_{2} < \infty$,
substantially improving on the bound of $O(n^{5} \log(n)^{2})$ by Jiang. Our
methods may also be applied to other high dimensional Gibbs samplers with
constraints and thus are of independent interest. In addition to giving
analytical bounds on the mixing time, our approach allows us to compute
rigorous estimates of the mixing time by simulating the eigenvalues of a random
matrix.
