  As our nearest large neighbor, the Andromeda Galaxy provides a unique
laboratory for investigating galaxy formation and the distribution and
substructure properties of dark matter in a Milky Way-like galaxy. Here, we
propose an initial 2-epoch ($\Delta t\approx 5$yr), 2-band Roman survey of the
entire halo of Andromeda, covering 500 square degrees, which will detect nearly
every red giant star in the halo (10$\sigma$ detection in F146, F062 of 26.5,
26.1AB mag respectively) and yield proper motions to $\sim$25 microarcsec/year
(i.e., $\sim$90 km/s) for all stars brighter than F146 $\approx 23.6$ AB mag
(i.e., reaching the red clump stars in the Andromeda halo). This survey will
yield (through averaging) high-fidelity proper motions for all satellites and
compact substructures in the Andromeda halo and will enable statistical
searches for clusters in chemo-dynamical space. Adding a third epoch during the
extended mission will improve these proper motions by $\sim t^{-1.5}$, to
$\approx 11$ km/s, but this requires obtaining the first epoch in Year 1 of
Roman operations. In combination with ongoing and imminent spectroscopic
campaigns with ground-based telescopes, this Roman survey has the potential to
yield full 3-d space motions of $>$100,000 stars in the Andromeda halo,
including (by combining individual measurements) robust space motions of its
entire globular cluster and most of its dwarf galaxy satellite populations. It
will also identify high-velocity stars in Andromeda, providing unique
information on the processes that create this population. These data offer a
unique opportunity to study the immigration history, halo formation, and
underlying dark matter scaffolding of a galaxy other than our own.
