  Matrix Product Vectors form the appropriate framework to study and classify
one-dimensional quantum systems. In this work, we develop the structure theory
of Matrix Product Unitary operators (MPUs) which appear e.g. in the description
of time evolutions of one-dimensional systems. We prove that all MPUs have a
strict causal cone, making them Quantum Cellular Automata (QCAs), and derive a
canonical form for MPUs which relates different MPU representations of the same
unitary through a local gauge. We use this canonical form to prove an Index
Theorem for MPUs which gives the precise conditions under which two MPUs are
adiabatically connected, providing an alternative derivation to that of
[Commun. Math. Phys. 310, 419 (2012), arXiv:0910.3675] for QCAs. We also
discuss the effect of symmetries on the MPU classification. In particular, we
characterize the tensors corresponding to MPU that are invariant under
conjugation, time reversal, or transposition. In the first case, we give a full
characterization of all equivalence classes. Finally, we give several examples
of MPU possessing different symmetries.
