  Most massive stars end their lives as Red Supergiants (RSGs), a short-lived
evolution phase when they are known to pulsate with varying amplitudes. The RSG
period-luminosity (PL) relation has been measured in the Milky Way, the
Magellanic Clouds and M33 for about 120 stars in total. Using over 1500 epochs
of R-band monitoring from the Palomar Transient Factory (PTF) survey over a
five-year period, we study the variability of 255 spectroscopically cataloged
RSGs in M31. We find that all RGSs brighter than M_K~ -10 mag
(log(L/L_sun)>4.8) are variable at dm_R>0.05 mag. Our period analysis finds 63
with significant pulsation periods. Using the periods found and the known
values of M_K for these stars, we derive the RSG PL relation in M31 and show
that it is consistent with those derived earlier in other galaxies of different
metallicities. We also detect, for the first time, a sequence of likely
first-overtone pulsations. Comparison to stellar evolution models from MESA
confirms the first overtone hypothesis and indicates that the variable stars in
this sample have 12 M_sun<M<24 M_sun. As these RSGs are the immediate
progenitors to Type II-P core-collapse supernovae (SNe), we also explore the
implication of their variability in the initial-mass estimates for SN
progenitors based on archival images of the progenitors. We find that this
effect is small compared to the present measurement errors.
