6.1-final-2012-b¶
Final Exam, 2012 · Section 6.1: Introduction to Eigenvalues : Ax = λx Source: finalexam_2.pdf, pp. 64-65
Problem¶
5 (12 pts.) Given a vector \(x\) in \(\mathbb{R}^n\), we can obtain a new vector \(y = \mathrm{cumsum}(x)\), the cumulative sum, by the following recipe:
\[
y_1 = x_1, \qquad y_j = y_{j-1} + x_j \ \text{ for } j = 2, \dots, n.
\]
(a) (7 pts.) What is the Jordan form of the matrix of this linear transformation?
(b) (5 pts.) For every \(n\), find an eigenvector of cumsum.
Solution
(a) The matrix of the transformation sends \(e_1 = (1, 0, \dots, 0)\) to \((1, 1, \dots, 1)\), and the other columns are found the same way: \[ A = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 1 & 1 & 0 & \cdots & 0 & 0 \\ 1 & 1 & 1 & \ddots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \ddots & 0 & 0 \\ 1 & 1 & 1 & \cdots & 1 & 0 \\ 1 & 1 & 1 & \cdots & 1 & 1 \end{bmatrix}. \] \(A\) is lower triangular with all diagonal entries equal to 1, so its only eigenvalue is 1, with algebraic multiplicity \(n\). To determine the Jordan form we need the geometric multiplicity of \(\lambda = 1\). The matrix \[ A - I_n = \begin{bmatrix} 0 & 0 & 0 & \cdots & 0 & 0 \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 1 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 1 & 1 & \cdots & 1 & 0 & 0 \\ 1 & 1 & \cdots & 1 & 1 & 0 \end{bmatrix} \] has rank \(n - 1\) (its transpose is already in echelon form with \(n - 1\) pivots), so the eigenspace for \(\lambda = 1\) is 1-dimensional. Hence the Jordan form is a single Jordan block: \[ J = \begin{bmatrix} 1 & 1 & & & \\ & 1 & 1 & & \\ & & 1 & \ddots & \\ & & & \ddots & 1 \\ & & & & 1 \end{bmatrix} \] (the empty entries are zeroes; \(A\) itself is not the identity, so the Jordan form cannot be \(I_n\)). (b) An eigenvector for \(A\) is a vector in the nullspace of \(A - I_n\). Only the last column of \(A - I_n\) is free, so every eigenvector is a scalar multiple of \[ e_n = \begin{bmatrix} 0 \\ \vdots \\ 0 \\ 1 \end{bmatrix}. \] Indeed cumsum leaves \(e_n = (0, \dots, 0, 1)\) unchanged. (For \(n = 1\), the same answer gives \(e_1 = (1)\).)Keywords: cumulative sum, Jordan form, Jordan block, eigenvector