Re: [obm-l] obm - U

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Tue, Oct 21, 2003 at 08:58:16AM -0200, marcio.lis wrote:
>   Alguem poderia me informar alguma coisa sobre o q o 
> pessoal andou fazendo na obm U informações sobre as 
> soluções tbm seriam interessantes.Gostaria de saber se 
> no 3 oa cardinalidade de xp=(p^2+2p+2)^2 e se no caso 
> 2x2 ficap^2+2p+2.

O problema 3, nível U, é de minha autoria.
Repetindo o enunciado, devemos contar as matrizes quadradas A
de tamanho 4x4 com coeficientes em Z/(p) que satisfazem A^2 = I (p > 2).

Uma matriz A em K^(nxn), onde K é um corpo qq,
satisfaz A^2 = I se e somente se K^n pode ser decomposto
em dois subespaços U e V com interseção zero e soma K^n
tais que A restrito a U (resp V) é a identidade (menos a id).

Estes dois subespaços são os autoespaços associados aos autovalores 1 e -1.
Como o polinômio mínimo não tem raiz dupla, A é semisimples (diagonalizável).

O importante é notar que há uma bijeção natural entre matrizes
satisfazendo A^2 = I e pares de subespaços U e V como acima.
Neste ponto dá para contar na marra ou dá para saber ou criar
um pouco mais de teoria.

Na marra, você contaria para cada valor da dimensão de U.
Temos 2 soluções triviais com dim U = 0 e dim U = 4 (-I e I).
No caso dim U = 1, primeiro escolhemos U: há (p^4 - 1) geradores
possíveis para U mas precisamos identificar vetores que são múltiplos
constantes um do outro, ou seja, precisamos dividir por (p - 1) 
para concluir que há (p^3 + p^2 + p + 1) subespaços de dimensão 1.
Escolha um subespaço complementar V_0 fixo qq:
um espaço complementar V pode ser identificado com o gráfico
de uma transformação linear de V_0 em U,
ou seja, para cada U há (p^3) espaços complementares V.
O caso dim U = 3 é análogo.
Até aqui somamos 2 p^6 + 2 p^5 + 2 p^4 + 2 p^3 + 2 e falta o caso dim U = 2.

Para escolher um subespaço U de dim 2, vamos primeiro escolher uma base.
Temos (p^4 - 1) escolhas para o primeiro vetor e (p^4 - p) escolhas
para o segundo. Por outro lado, dado um subespaço de dim 2,
quantas bases ele tem? Agora temos (p^2 - 1) escolhas para o primeiro
vetor e (p^2 - p) escolhas para o segundo. Assim, o número de subespaços U é
((p^4 - 1)(p^4 - p))/((p^2 - 1)(p^2 - p)) = p^4 + p^3 + 2p^2 + p + 1.
Novamente, para cada U escolha um complementar V_0 fixo qq:
um espaço complementar V pode ser identificado com o gráfico
de uma transformação linear de V_0 em U,
ou seja, para cada U há (p^4) espaços complementares V.
Ou seja, o caso dim U = 2 contribui com p^8 + p^7 + 2 p^6 + p^5 + p^4
e a resposta final do problema é

 p^8 + p^7 + 4 p^6 + 3 p^5 + 3 p^4 + 2 p^3 + 2

Para resolver o caso geral (em vez do caso 4x4),
ajuda muito saber contar subespaços de dimensão b de F_q^a,
onde q é uma potência de primo, F_q é o corpo finito de q elementos,
e a e b são inteiros não negativos. Este problema é tão importante
que a resposta tem nome, e escreve-se assim:

   ( a )
   (   )
   ( b )q

ou seja, o símbolo de binomial com um q embaixo; eu vou escrever binom(a,b;q).
Lendo o que eu escrevi acima não é muito difícil concluir que

                     (q^a - 1)(q^(a-1) - 1)(q^(a-2) - 1)...(q - 1)
 binom(a,b;q) = ----------------------------------------------------------
                 (q^b - 1)(q^(b-1) - 1)...(q - 1) (q^(a-b) - 1)...(q - 1)

Não é muito difícil provar que isto é um polinômio em q com coeficientes
inteiros não negativos. A notação talvez fique menos misteriosa observando
que binom(a,b;1) = binom(a,b). Há outras interpretações para binom(a,b;q),
o meu livrinho do colóquio (matemática quântica) pode servir como referência.

Voltando ao problema da OBM, a resposta do problema para matrizes nxn
com coeficientes em F_q é

 somatório_k q^(k(n-k)) binom(n,k;q).

Em particular, se n = 2 temos

 1 + q (q+1) + 1 = q^2 + q + 2.

No caso q = 2^k o início do problema quebra pois (x^2 - 1) = (x - 1)^2
em característica 2, ou seja, a matriz deixa de ser diagonalizável.
O problema fica totalmente diferente.

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================