PROVA DE MATEMÁTICA DISCRETA 2O. SEMESTRE DE 2003

Instruções. Esta prova é individual, mas naturalmente você pode consultar suas anotações, livros, etc. Entregue a soluções das questões 1 e 2 até as 14:00. Entregue as demais soluções até as 20:00 do dia 4/03/2004, em minha sala, quando faremos uma pequena entrevista.

1. Prove o seguinte lema: For any symmetric matrix A = (A_{ij})_{1≤i,j≤n}, we have

rk(A) ≥ \frac{(tr(A))^{2}}{tr(A^{2})} = \frac{(∑_{1≤i≤n} A_{ii})^{2}}{∑_{1≤i,j≤n} A_{ij}^{2}} .  (1)

Consequently, if A_{ii} = 1 for all i and |A_{ij}| ≤ ε for all i ≠ j, then

rk(A) ≥ \frac{n}{1 + ε^{2}(n − 1)}.  (2)

In particular, if ε = \sqrt{1/n}, then rk(A) ≥ n/2. [Sugestão. Let r = rk(A). Show that A has r non-zero eigenvalues, say, λ_{1}, …, λ_{r}. Apply Cauchy–Schwarz to deduce that

(tr(A))^{2} = (λ_{1} + ⋯ + λ_{r})^{2} ≤ r(λ_{1}^{2} + ⋯ + λ_{r}^{2}) = r tr(A^{2}).

Now use that A is symmetric and compute tr(A^{2}). ]

2. Aplique o lema acima para encontrar uma cota superior para o número máximo de vetores unitários v_{1}, …, v_{m} ∈ ℝ^{n} com |⟨v_{i}, v_{j}⟩| ≤ 1/100\sqrt{n} para todo i ≠ j. [Sugestão. Considere a matrix m × m cujas entradas são ⟨v_{i}, v_{j}⟩.]

3. Escolha dois problemas da lista 1. (A sua nota dependerá de sua escolha: exercícios muito simples valem pouco.)

4. Escolha um problema da lista 2. (Idem.)

Date: Versão de 3 de março de 2004.