Fun linear algebra solutions, part 1

April 2013

Someone pointed out that my “fun linear algebra problems” post would be more useful with solutions. Here’s a solution to problems 1 and 2. (My favorite solution to problem 1 part (c) requires some group theory, so it isn’t suitable for beginning linear algebraists, but there are mildly more annoying ones using only linear algebra.)

Problem 1

Let \(\mathbb{F}\) be the finite field of \(p^k\) elements. Let \(V\) be a \(n\)-dimensional vector space over \(\mathbb{F}\).

a. How many linear transformations \(T: V \to V\) are there?

b. How many of these are invertible?

(a) Linear maps \(T: V \to V\) are in bijection with \(n \times n\) matrices over the field \(\mathbb{F}\). Each matrix entry has \(p^k\) possibilities so the total number of matrices is $$p^{kn^2}.$$

(b) Recall that \(T\) is invertible iff it maps a basis to another basis. Then there are as many invertible maps as there are bases of \(V\). Imagine picking such a basis \(e_1, \dots, e_n\) sequentially; we will count how many possibilities there are for each choice.

When picking vector \(e_i\), it may not be in the span of \(e_1, \dots, e_{i-1}\), or we get linear dependence again. That span is a vector space of dimension \(i-1\), so it has \(|\mathbb{F}|^{i-1}\) elements. Any of the other vectors in \(V\) are available to pick, so there are \(|V| - |\mathbb{F}|^{i-1}\) possibilities. (This also holds for \(i=1\) if we define the span of the empty set to be the zero-dimensional vector space.)

Multiplying the number of possibilities for each vector together, we get \(\prod_{i=1}^n |\mathbb{F}|^n - |\mathbb{F}|^{i-1}\) or, simplifying, $$\prod_{i=0}^{n-1} (p^{kn} - p^{ki}).$$

(c) Let \(GL(V)\) denote the set of invertible maps \(V \to V\); let \(SL(V)\) denote the subset of such maps of determinant 1. Note that \(GL(V)\) is a group with composition as the group law, and that \(\det : GL(n) \to \mathbb{F}^\times\) is a group homomorphism whose kernel is \(SL(V)\). Then \(SL(V)\) is a normal subgroup of \(GL(V)\) of index \(|\mathbb{F}^\times| = p^k - 1\), so $$|SL(V)| = |GL(V)|/(p^k-1).$$

Problem 2

Let $[f_n] be the $[n]th Fibonacci number.

  1. Find a linear transformation $[T : \mathbb{R}^2 \to \mathbb{R}^2] such that $[T(f_{n-1}, f_{n}) = (f_n, f_{n+1})] for all $[n]. Write down the matrix of $[T] with respect to the standard basis.
  2. Find an algorithm for determining the $[n]th Fibonacci number in $[O(\log n)] time rather than the typical $[O(n)] (assuming addition and multiplication are $[O(1)]).
  3. What are the eigenvalues of $[T]?
  4. Derive the closed-form expression for the $[n]th Fibonacci number.

(a) The desired map is \(T(x, y) = (y, x+y)\); its matrix is $$M = \left(\begin{array}{cc}0 & 1 \\\\ 1 & 1\end{array}\right)$$

(b) We have \(f_n\) is the first coordinate of \(T^n(0, 1)\), so we can compute \(f_n\) if we can compute \(M^n\). Multiplying \(2 \times 2\) matrices is constant time, so using repeated squaring we can compute \(M^n\) in logarithmic time.

(c) The characteristic polynomial of \(M\) is \(x^2 - x - 1\), so the eigenvalues are \(\frac{1 \pm \sqrt{5}}{2} = \\{\phi, 1-\phi\\}\) (where \(\phi\) is the golden ratio).

(d) The eigenvectors of \(T\) are \((1, \phi)\), corresponding to the eigenvalue \(\phi\), and \((1, 1-\phi)\) with eigenvalue \((1-\phi)\). We can decompose \((0, 1) = \frac{(1, \phi) - (1, 1-\phi)}{\sqrt{5}}\). Then $$T^n(0, 1) = T^n\left(\frac{(1, \phi) - (1, 1-\phi)}{\sqrt{5}}\right) = \frac{\phi^n(1, \phi) + (1-\phi)^n(1, 1-\phi))}{\sqrt{5}},$$ and for the closed-form expression we get $$f_n = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}.$$


Enjoyed this post? Get notified of new ones via email or RSS. Or comment:

email me replies

format comments in markdown.