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