Problem Set #10 Part B Official Solutions Total Points: 51

Inna Zakharevich

(5) 1. We know that if

e_{i} = ∑_{j=1}^{n} a_{ij}f_{j} f_{i} = ∑_{j=1}^{n} b_{i}je_{j}

then A = (a_{ij}) and B = (b_{ij}). Plugging in the definition for f_{j} into the first sum we see that

e_{i} = ∑_{j=1}^{n} a_{ij} ∑_{k=1}^{n} b_{jk}e_{k} ⟹ e_{i} = ∑_{j=1}^{n} (∑_{k=1}^{n} a_{ik}b_{kj}) e_{j}.

However, we also know that the e_{i} are linearly independent; thus we see that

∑_{k=1}^{n} a_{ij}b_{jk} = \{ \begin{matrix}1 & if i = j \\ 0 & otherwise \end{matrix}

However, these are also the entries of the matrix AB; thus we see that AB = Id. By plugging in the definition for e_{j} into the sum for f_{i} we get that BA = Id.

(9) 2.

(2) (1) Consider a polynomial in V. This will be written as a sum of monomials with x taken to powers from 0 to n − 1; thus every polynomial is a linear combination of the vectors {1, x, …, x^{n−1}}, so this is a basis. The map f : P (x) ↦ P (x + 1) maps any monomial to a polynomial of the same degree. Thus the map will map a polynomial of degree at most n − 1 to a polynomial of degree at most n − 1, so it is a map from V to itself. Notice that f(λP (x)) = λP (x + 1) = λf(P (x)), and f(P (x) + Q(x)) = P (x + 1) + Q(x + 1) = f(P (x)) + f(Q(x)), so we see that the map is linear.

(2) (2) Notice that f(x^{m}) = ∑_{i=1}^{m} \binom{m}{i}x^{i}, so it follows that the matrix for M in terms of

the monomials x^{i} is (\binom{i−1}{j−1}), where \binom{a}{b} = 0 if b > a.

(5) (3) From problem 1 we see that all we need to do is calculate the matrix for the basis {x^{i}} in terms of the basis {(x + 1)^{i}}. We claim that

x^{m} = ∑_{i=0}^{m}(−1)^{m−i}\binom{m}{i}(x + 1)^{i}.

We will do this by calculating algorithmically, and using induction. First note that for any a > m, the coefficient of (x + 1)^{a} will be 0. Since (x + 1)^{m} is the only polynomial of degree greater than or equal to m left, we have that the coefficient of (x + 1)^{m} is 1. Now, starting with (x + 1)^{m} we will systematically eliminate the highest-degree monomial (other than x^{m}); the coefficient of x^{a} will be the coefficient of this monomial at the n − a-th step. We start with (x + 1)^{m}; the coefficient of x^{m−1} is m. Thus the coefficient of (x + 1)^{m−1} will be −\binom{m}{m−1}, as stated. Now suppose that for all of m − 1, …, a the coefficients were (−1)^{m−i}\binom{m}{i}. Then we claim that the coefficient of x^{a−1} in

∑_{i=0}^{m−a}(−1)^{i}\binom{m}{m − i}(x + 1)^{m−i}

is (−1)^{m−a}\binom{m}{a−1}. Then we will know that the coefficient of (x + 1)^{a−1} will be the negative of that, and we will have shown the result. Indeed, the coefficient is

∑_{i=0}^{m−a}(−1)^{i}\binom{m}{m − i}\binom{m − i}{a − 1} = \binom{m}{a − 1} ∑_{i=0}^{m−a}(−1)^{i}\binom{m − a + 1}{i}

= (−1)^{m−a+1}\binom{m}{a − 1}

as desired. Thus we have shown the formula for x^{m} in terms of (x + 1)^{i}, so we know that

M^{−1} = ((−1)^{i−j}\binom{i − 1}{j − 1}) .

(10) 3.

(5) (1) Solution 1: We will prove this claim by induction. Clearly if n = 1 the set {exp(α_{i}x)} is linearly independent. Suppose that with n − 1 distinct α_{i} the set is linearly independent, but with n it isn’t for some α_{i}. Then we have that for some a_{i}, ∑_{i=1}^{n} a_{i} exp(α_{i}x) = 0, for all x. Differentiating, we get that ∑_{i=1}^{n} a_{i}α_{i} exp(α_{i}x) = 0 for all x. Multiplying the first of these by α_{1} and subtracting, we get that ∑_{i=2}^{n}(α_{1} − α_{i})a_{i} exp(α_{i}x) = 0. By the induction hypothesis we know that (α_{1} − α_{i})a_{i} = 0, and since all of the α_{i} are distinct this means that a_{i} = 0 for i ≥ 2. Thus a_{1} = 0 also, and we have shown that any n are linearly independent, and the claim follows.

Solution 2: Let V be the space of all C^{∞} functions from R to R. We know that differentiation is a linear function on this space. Also, (exp(α_{i}x))′ = α_{i} exp(α_{i}x), so exp(α_{i}x) is an eigenvector of this operator. If the α_{i} are distinct then the set {exp(α_{1}x), …, exp(α_{n}xO)} is a set of eigenvectors with different eigenvalues, which we already know is linearly independent.

(5) (2) Without loss of generality we will assume that α_{n} is the largest α_{i}. Then for some open interval I containing α_{n} no other α_{i} is contained in I. Then we know that for i < n |x − α_{i}| is differentiable inside I. Suppose that for some a_{1}, …, a_{n} we have ∑_{i=1}^{n} a_{i}|x − α_{i}| = 0. Then this is also true inside I. Then the function (∑_{i=1}^{n−1} a_{i}|x − α_{i}|)′ is differentiable and constant in this interval. It should be equal to −a_{n}|x − a_{n}|′ on the set I − {a_{n}}. However, unless a_{n} = 0 −a_{n}|x − a_{n}|′ is nonconstant on this set. Thus we see that a_{n} = 0. By induction we conclude that all of the coefficients must be 0, and we see that the set is linearly independent.

(10) 4.

(5) (1) Suppose that such a v exists. Thus we have w = vu. Suppose that x ∉ ker w. Then vux ≠ 0, so ux ≠ 0 so x ∉ ker u. Thus ker u ⊆ ker v. Now suppose that ker u ⊆ ker w. Let {u_{1}, …, u_{n}} be a basis for U such that {u_{1}, …, u_{m}} (n ≥ m) is a basis for ker u, and {u_{1}, …, u_{m′}} is a basis for ker w (m′ ≥ m) (this is possible because ker u ⊆ ker w). Consider uu_{1}, …, uu_{n}. Let {v_{1}, …, v_{k}} be linearly independent and such that {uu_{m+1}, …, uu_{n}, v_{1}, …, v_{k}} contains a basis, and such that {uu_{i}, v_{1}, …, v_{k}} is linearly independent for all i > m. Then let v be the transformation that sends uu_{i} to wu_{i} for n ≤ i > m and v_{i} to 0 for 1 ≤ i ≤ k. This transformation will be well-defined unless some {uu_{i_{1}}, …, uu_{i_{l}}} are not linearly independent for i_{j} > m′. We will show that the set {uu_{m′+1}, …, uu_{n}} is linearly inependent. Suppose that it is not. Then we have a_{i} such that ∑_{i=m′+1}^{n} a_{i}uu_{i} = 0. However, this means that u (∑_{i=m′+1}^{n} a_{i}u_{i}) = 0, which does not occur unless all of the a_{i} = 0 because we are only looking at vectors outside of the kernel of u. Thus we have a transformation v such that uv = w on a basis for U, so we know that uv = w.

(5) (2) Suppose that such a u exists. Then if x ∈ im w we know that there is some y ∈ U such that wy = x, so v(uy) = x, so x ∈ im v. Thus im w ⊆ im v. Now suppose that im w ⊆ im v. Let {v_{1}, …, v_{n}} be a basis for V such that {vv_{1}, …, vv_{m}} (m ≤ n) is a basis for im v, and {vv_{1}, …, vv_{l}} (l ≤ m) is a basis for im w (this is possible because im w ⊆ im v). Then let {u_{1}, …, u_{m′}} be a basis for U. Notice that m′ ≥ l because l is the dimension of im w. Then if we define uu_{i} = v_{i} for 1 ≤ i ≤ l and 0 otherwise, we will have uv = w.

(17) 5.

(5) (1) Let T be the linear transformation that M represents with a standard basis in K^{n}. Then T is invertible if and only if M is invertible. Suppose that T is invertible. Then we know that it is a surjection onto a basis of K^{n}, so rank T = n, so rank M = n. Now suppose that rank M = n. Then rank T = n. Suppose that T x = T y. Then T (x − y) = 0. Consider a basis for K^{n} with x − y as the first vector. Then the dimension of the image would be at most n − 1 (since the first vector of the basis is mapped to 0) so the rank is at most n − 1. Contradiction. Thus such a basis does not exist, so x = y. Thus T is injective, and therefore invertible, so M is also invertible.

(5) (2) Suppose that for every 1 ≤ k ≤ n we have that the dimension of the subspace generated by C_{1}, …, C_{k} is k. Then in particular this is true for k = n so the rank of M is n. Thus M is invertible, by the first part. Now suppose that M is invertible. This means that {e_{i}T } is linearly independent. In particular, {e_{1}T, …, e_{k}T } is linearly independent for 1 ≤ k ≤ n. Note that e_{i}T = C_{i}, so we see that C_{1}, …, C_{k} are linearly independent.

(2) (3) We have n^{2} spots in the matrix. Each spot can be filled by one of p elements of Z/pZ, so there are p^{n^{2}} such matrices.

(5) (4) We will first show that there are p^{k} vectors in a k-dimensional subspace of K^{n}. Let U ⊆ K^{n} be a k-dimensional subspace. Then we know there exists an invertible matrix M that maps U to the subspace K^{k}. Since U is bijective and we know that K^{k} has p^{k} elements, we see that U contains p^{k} elements. Now we will count the number of invertible matrices M. By parts 1 and 2, a matrix M is invertible if and only if the first k rows are linearly independent for all k. Thus we will count the number of such M by counting the number of ways to pick a new vector to add to the matrix. There will be p^{i−1} such vectors, so there are p^{i−1} choices of entries that we can’t make in order to make the first i rows linearly independent. Thus there will be ∏_{i=1}^{n}(p^{n^{2}} − p^{i−1}) invertible matrices.