I have an n-by-p matrix $X$ and I consider the eigenvalues of the p-by-p matrix $X^{'}X$. Let's denote the largest and smallest eigenvalues of $X^{'}X$ with the usual notation $\lambda_{1}(X^{'}X)$ and $\lambda_{p}(X^{'}X)$.
I now form a new matrix from a subset $\gamma$ of the columns of $X$, call it $X_{\gamma}$. For instance if $\gamma=\left\{ 1,4,5\right\}$ then $X_{\gamma}$ is formed by joining columns 1 4 and 5.
I want to consider the eigenvalues of $X_{\gamma}^{'}X_{\gamma}$.
I think it is true that
$\lambda_{p}(X^{'}X) \leq \lambda_{p}(X_{\gamma}^{'}X_{\gamma}) \leq \lambda_{1}(X_{\gamma}^{'}X_{\gamma}) \leq\lambda_{1}(X^{'}X)$,
but I would like to prove or disprove this claim. Can anyone suggest a proof?
You can use the Rayleigh quotient (see here: http://en.wikipedia.org/wiki/Rayleigh_quotient). This works as follows.
Let $A$ be a real symmetric matrix with minimal eigenvalue $\mu_\min$ and maximal eigenvalue $\mu_\max$. Then we have $$ \mu_\min = \min_{v^Tv=1}v^TAv $$ $$ \mu_\max = \max_{v^Tv=1}v^TAv $$ This is easy to see if we transform $A$ into diagonal form via an orthogonal transformation. This is possible since $A$ is normal.
On to your particular situation. Let $$ \gamma = \{\gamma_1,\ldots,\gamma_m\}\ with\ m \in \mathbb N\ and\ \gamma_1 < \cdots < \gamma_m $$ be the set of indices of the columns of $X$ we're interested in. Observe that the matrix $X_\gamma^TX_\gamma$ is a submatrix of $X^TX$. Namely, $X_\gamma^TX_\gamma$ consists of the rows and columns of $X^TX$ indexed by the elements of $\gamma.$ With this in mind, let's define the projection $$ \tilde\cdot:\mathbb R^p \rightarrow \mathbb R^m, y = (y_1,\ldots,y_p)^T \mapsto \tilde y = (y_{\gamma_1},\ldots,y_{\gamma_m})^T $$ Moreover, let's define the set of column vectors $$ V_\gamma = \left\{x = (x_1,\ldots,x_p)^T \in \mathbb R^p \mid x^Tx = 1\ and\ \forall j \not\in \gamma: x_j = 0 \right\}. $$ Note that $$ \widetilde{V_\gamma} = \{y \in \mathbb R^m \mid y^Ty = 1\}. $$ Furthermore, from all these definitions and constructions, we see that $$ \forall v \in V_\gamma: v^TX^TXv = (\tilde v)^TX_\gamma^TX_\gamma\tilde v. $$ By combining all this, we get $$ \begin{align*} \lambda_p(X_\gamma^TX_\gamma) & = \min_{\{y \in \mathbb R^m \mid y^Ty = 1\}}y^TX_\gamma^TX_\gamma y \\ & = \min_{v \in V_\gamma}(\tilde v)^TX_\gamma^TX_\gamma\tilde v \\ & = \min_{v \in V_\gamma}v^TX^TXv \\ & \geq \min_{\{v \in \mathbb R^p \mid v^Tv = 1\}} v^TX^TXv \\ & = \lambda_p(X^tX) \end{align*} $$ and similarly $$ \begin{align*} \lambda_1(X_\gamma^TX_\gamma) & = \max_{\{y \in \mathbb R^m \mid y^Ty = 1\}}y^TX_\gamma^TX_\gamma y \\ & = \max_{v \in V_\gamma}(\tilde v)^TX_\gamma^TX_\gamma\tilde v \\ & = \max_{v \in V_\gamma}v^TX^TXv \\ & \leq \max_{\{v \in \mathbb R^p \mid v^Tv = 1\}} v^TX^TXv \\ & = \lambda_1(X^tX), \end{align*} $$ as desired.