18.700 Problem Set 3

Due in class Monday October 23; late work will not be accepted. Your work on graded problem sets should be entirely your own.

1. (10 points) Suppose a, b, c, and d are elements of a field 𝔽. Use elementary row and column operations to calculate

det ( \begin{matrix}1 & a & a^{2} & a^{3} \\ 1 & b & b^{2} & b^{3} \\ 1 & c & c^{2} & c^{3} \\ 1 & d & d^{2} & d^{3} \end{matrix} ) .

Under what conditions on a, b, c, and d is this determinant non-zero? (As a check on your work, the answer to this last question is fairly simple.)

2. (10 points) Suppose the field 𝔽 is ℤ/2ℤ = {0, 1}. You can think of choosing a vector in 𝔽^{n} “at random” by flipping a coin n times, and putting a 0 for each coordinate where you get a heads, and a 1 where you get tails. In the same way, you can make a random n×n matrix by flipping n^{2} times. Each of the 2^{n^{2}} matrices has an equal chance to appear. The determinant of such a matrix is 0 or 1. This problem looks at which determinant is more likely; that is, at whether a random matrix is “likely” to be invertible.

a) How many of the 16 2 × 2 matrices have determinant 1?

b) (This one is hard.) Suppose that A is an (n − 1) × n matrix (over ℤ/2ℤ) of rank exactly n − 1. Show that there are exactly 2^{n−1} row vectors v ∈ 𝔽^{n} with the

property that the n × n matrix ( \begin{matrix}A \\ v \end{matrix} ) is invertible.

c) Explain why less than half of all n × n matrices are invertible.

3. (10 points) This problem is about square matrices A with integer entries, whose inverses also have integer entries. The only 1 × 1 matrices of this type are (±1)

a) Suppose A = ( \begin{matrix}p & n \\ 0 & q \end{matrix} ), with p, q, and n integers. Show that A^{−1} has integer

entries if and only if p and q are both ±1.

b) Suppose A = ( \begin{matrix}n & p \\ q & 0 \end{matrix} ), with p, q, and n integers. Show that A^{−1} has integer

entries if and only if p and q are both ±1.

c) Give an example of a 2 × 2 matrix A with integer entries, none of which is ±1, such that A^{−1} exists and has integer entries.