  We present the surface brightness profile of M31's stellar halo out to a
projected radius of 175 kpc. The surface brightness estimates are based on
confirmed samples of M31 red giant branch stars derived from Keck/DEIMOS
spectroscopic observations. A set of empirical spectroscopic and photometric
M31 membership diagnostics is used to identify and reject foreground and
background contaminants. This enables us to trace the stellar halo of M31 to
larger projected distances and fainter surface brightnesses than previous
photometric studies. The surface brightness profile of M31's halo follows a
power-law with index -2.2 +/- 0.2 and extends to a projected distance of at
least ~175 kpc (~ 2/3 of M31's virial radius), with no evidence of a downward
break at large radii. The best-fit elliptical isophotes have b/a=0.94 with the
major axis of the halo aligned along the minor axis of M31's disk, consistent
with a prolate halo, although the data are also consistent with M31's halo
having spherical symmetry. The fact that tidal debris features are
kinematically cold is used to identify substructure in the spectroscopic fields
out to projected radii of 90 kpc, and investigate the effect of this
substructure on the surface brightness profile. The scatter in the surface
brightness profile is reduced when kinematically identified tidal debris
features in M31 are statistically subtracted; the remaining profile indicates a
comparatively diffuse stellar component to M31's stellar halo exists to large
distances. Beyond 90 kpc, kinematically cold tidal debris features can not be
identified due to small number statistics; nevertheless, the significant
field-to-field variation in surface brightness beyond 90 kpc suggests that the
outermost region of M31's halo is also comprised to a significant degree of
stars stripped from accreted objects.
