Page 302 - 35Linear Algebra

302 Kernel, Range, Nullity, Rank

3
ii. Give some method for choosing a random bit vector v in B . Sup-
3
pose S is a collection of 2 linearly independent bit vectors in B .
How can we tell whether S ∪ {v} is linearly independent? Do you
think it is likely or unlikely that S ∪ {v} is linearly independent?
Explain your reasoning.
iii. If P is the characteristic polynomial of a 3 × 3 bit matrix, what
must the degree of P be? Given that each coefficient must be
either 0 or 1, how many possibilities are there for P? How many
of these possible characteristic polynomials have 0 as a root? If M
is a 3×3 bit matrix chosen at random, what is the probability that
it has 0 as an eigenvalue? (Assume that you are choosing a random
matrix M in such a way as to make each characteristic polynomial
equally likely.) What is the probability that the columns of M
3
form a basis for B ? (Hint: what is the relationship between the
kernel of M and its eigenvalues?)
Note: We could ask the same question for real vectors: If I choose a real
vector at random, what is the probability that it lies in the span
of some other vectors? In fact, once we write down a reasonable
way of choosing a random real vector, if I choose a real vector in
n
R at random, the probability that it lies in the span of n − 1
other real vectors is zero!

302