MATHEMATICS 152, FALL 2003METHODS IN DISCRETE MATHEMATICSOutline #8 (Linear Algebra over Finite Fields)We review important topics from linear algebra, with an emphasis on vectorspaces and matrices defined over finite fields.Biggs presupposes a knowledge of linear algebra, and so there is no relevantreading. You will probably find it useful to consult whatever linear algebratextbook you own.1. Given any field F , recall the vector space V = {(a1, . . . , an)|ai∈ F, ∀i}.This is a vector space of dimension n over F . State the definitions ofsubspace, linear independence, span, basis, and dimension.2. Given the finite field F = Fqwith q = pkelements, what is |V |, thenumber of elements of V as defined above? How many one-dimensionalsubspaces of V are there? List them for the case where q = 3 and n = 2.3. State the definition of a linear transformation T : V −→ V . Recall thatwe may represent such a linear transformation by an n × n matrix A,where T (v) = Av. Recall how to act on a vector by a matrix. If wewrite:v =x1...xnand A =a11. . . a1n......an1. . . ann,then we defineAv =a11x1+ · · · + a1nxn...an1x1+ · · · + annxn.Illustrate this with examples when F is a finite field and when n = 2.Choose one example where F is the field Z5and one where F is the fieldF4.4. Show that the collection of n × n matrices with entries from the field F ,denoted Mn(F ), forms a ring with appropriate notions of addition andmultiplication. When F = Fqis a finite field, what is |Mn(F )|?15. State the definitions of the kernel and image of a matrix/linear transfor-mation. Using the definition of a linear transformation, show that thekernel and image are subspaces of V .6. State the definition of the determinant of a 2 × 2 matrix. If A, B ∈Mn(F ), then the determinant satisfies the following facts:(a) det(AB) = det(A) det(B)(b) det(At) = det(A), where Atis the transpose of A.(c) det(A) 6= 0 if and only if A is invertible.Explain how the proof of these results (which you have seen in a previouscourse for the case of matrices over the field R) depends only on the factthat the entries in the matrix are from a field F . (Don’t take the timeto write out the proof!).Illustrate with examples of A and B when F is the finite field F4andwhen n = 2.7. Given a matrix A, define the notions of the eigenvalues and eigenvectorsof A. Define the characteristic polynomial of A,fA(λ) = det(A − λI),and show that its roots are precisely the eigenvalues of A. Illustrate withexamples when F is the finite field Z5and when n = 2 by finding theeigenvectors and eigenvalues of [3 42 0]8. Define the general linear group of matrices:GLn(F ) = {A ∈ Mn(F )| det(A) 6= 0}Show that, in fact, this is a group. For the case n = 2, determine theorder of this group when F = Fqis a finite field by counting the numbe rof possibilities for the top row of the matrix and then the number for thebottom row. Using the same strategy, determine the order of the groupwhen n = 3, then generalize the result to arbitrary n. The crucial stepis the bottom row for n = 3: choosing any linear combination of the toptwo rows would make the determinant zero.9. Define the following subgroup of GLn(F ):SLn(F ) = {A ∈ Mn(F )| det(A) = 1}, the special linear groupShow that, in fact, this is a group. Illustrate with examples when F isthe finite field Z5and when n = 2 by exhibiting two matrices (not theidentity) in SLn(Z5) and their product. What is the order of this groupwhen F = Fqis a finite field of order q and when n = 2 or n =