In exercise [1, p. 34 exercise 2.5] we are asked to show that the matrix \mathbf{R}=\sigma^2 \mathbf{I}+P_1\mathbf{e_1}\mathbf{e_1}^H+P_2\mathbf{e_2}\mathbf{e_2}^H is circulant when \mathbf{e_i}^H=\left[ {\begin{array}{*{20}c} 1 & {e^{-j2\pi f_i } } & {e^{-j2\pi (2f_i) } } & \cdots & {e^{-j2\pi (n - 1)f_i } } \end{array}} \right], i=1,2.
Solution: A matrix \mathbf{A} is circulant when its elements are arranged in the following way:
A=\left[ {\begin{array}{*{20}c} {a_0 } & {a_1 } & \cdots & {a_{n - 1} } \\ {a_{n - 1} } & {a_0 } & \cdots & {a_{n - 2} } \\ \vdots & \vdots & \vdots & \vdots \\ {a_1 } & {a_2 } & \cdots & {a_0 } \\ \end{array}} \right] (1)

Computing the dyad \mathbf{e_i}\mathbf{e_i}^H (for i=1,2) results in
\mathbf{e_i}\mathbf{e_i}^H=\left[ {\begin{array}{*{20}c} 1 \\ {e^{j2\pi f_i } } \\ \vdots \\ {e^{j2\pi (n - 1)f_i } } \\ \end{array}} \right] \cdot \left[ {\begin{array}{*{20}c} 1 & {e^{-j2\pi f_i } } & \cdots & {e^{-j2\pi (n - 1)f_i } } \end{array}} \right]
=\left[ {\begin{array}{*{20}c} 1 & {e^{ - j2\pi f_i } } & {e^{ - j2 \cdot 2\pi f_i } } & \cdots & {e^{ - j2(n - 1)\pi f_i } } \\ {e^{j2\pi f_i } } & 1 & \cdots & \cdots & {e^{ - j2(n - 2)\pi f_i } } \\ {e^{j2 \cdot 2\pi f_i } } & {e^{j2\pi f_i } } & 1 & \cdots & {e^{ - j2(n - 3)\pi f_i } } \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ {e^{j2(n - 1)\pi f_i } } & {e^{j2(n - 2)\pi f_i } } & {e^{j2(n - 3)\pi f_i } } & \cdots & 1 \\ \end{array}} \right]

We observe that this is a n \times n hermitian toeplitz matrix. In order to be circulant the elements e^{j2\pi f_i} and e^{ - j2(n - 1)\pi f_i }, e^{j2 \cdot 2\pi f_i} and e^{ - j2(n - 2)\pi f_i }, etc. have to be equal. Or in general that the following relation must hold:
e^{j2\cdot m \pi f_i}=e^{-j2(n-m) \pi f_i}, m=1,...,n-1. (2)

Because [1, p.22] f_i=\frac{l_i}{n} , \mathrm{i=1,2} where l_i are distinct integers in the range [-n/2,n/2-1] for n even or [-(n-1)/2, (n-1)/2] for n odd we can rewrite the right hand side of (2) as:
e^{-j2(n-m) \pi f_i} = e^{-j2n\pi f_i}\cdot e^{j2m\pi f_i} (3)

But
e^{-j2n\pi f_i}=e^{-j2n\pi\frac{l_i}{n}}=e^{-j2\pi l_i}=1 (4)

thus
e^{-j2(n-m) \pi f_i} = e^{j2m\pi f_i} (5)

which proofs that the dyad \mathbf{e_i}\mathbf{e_i}^H is circulant because relation (2) is satisfied. The matrix \mathbf{R}=\sigma^2 \mathbf{I}+P_1\mathbf{e_1}\mathbf{e_1}^H+P_2\mathbf{e_2}\mathbf{e_2}^H is circulant, as the product of a circulant matrix with a scalar is itself a circulant matrix, the identity matrix is a special form of a circulant matrix, and also the sum of circulant matrices is also a circulant matrix. QED.

[1] Steven M. Kay: “Modern Spectral Estimation – Theory and Applications”, Prentice Hall, ISBN: 0-13-598582-X.