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.

- 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.- 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)$`

).- What are the eigenvalues of
`$T$`

?- 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}}.$$`

## Comments