Document Text Contents
Page 1
1
Ælgebra linear
versão 78
28 de maio de 2014
jerônimo c. pellegrini
Page 196
Ve
rs
ão
Pr
el
im
in
ar
Ál
ge
br
a
Li
ne
ar
- n
ot
as
de
au
la
–
ve
rs
ão
78
Je
rô
ni
m
o
C.
Pe
lle
gr
in
i
6.6. APLICAÇÕES 183
Usaremos como exemplo a modelagem, extremamente simplificada, da evolução de uma doença. Su-
ponha que
Representamos o estado de um sistema em um processo estocástico como um vetor de estado. A evo-
lução do sistema é descrita por uma sequencia de vetores de estado, onde cada um pode depender, proba-
bilisticamente, dos anteriores.
Definição 6.66 (cadeia deMarkov). Se um sistema pode ser descrito em um dadomomento t por um vetor
de estados, e o estado no momento t+ 1 depende apenas do estado no momento t e de probabilidades de
transição entre estados, então a sequência de vetores de estado desse sistema é uma cadeia de Markov. �
Definição 6.67 (matriz de transição). Se, para cada par de estados i, j, a probabilidade de transição de i
para j é pij, então a matriz de transição da cadeia de Markov é dada por (pi,j), ou
P =
p11 p12 p13p21 p22 p23
p31 p32 p33
�
Exemplo 6.68. A matriz
P =
(
0.2 0.1 0.7
0.1 0.5 0.4
0.6 0.2 0.2
)
representa as probabilidades de transição em uma cadeia de Markov com tres estados. J
Um vetor estocástico é um vetor que representa uma distribuição de probabilidades.
Definição 6.69 (vetor estocástico). Um vetor v ∈ Rn é estocástico se P i vi = 1, e todos os vi são não-
negativos. �
Exemplo 6.70. Os vetores (1, 0, 0)T , (1/2, 1/2, 0)T e (1/4, 0, 3/4, 0)T são estocásticos. J
Definição 6.71 (matriz estocástica). Umamatriz é estocástica se todas as suas linhas ou todas as suas colu-
nas forem vetores estocásticos.
Se tanto as linhas como as colunas de uma matriz são vetors estocásticos, dizemos que a matriz é du-
plamente estocástica. �
Exemplo 6.72. Amatriz de transição de qualquer cadeia deMarkov é estocástica. Por exemplo, amatriz do
exemplo 6.68 é uma matriz estocástica, porque só tem entradas positivas e a soma de cada linha é um. J
As matrizes de transição são operadores lineares, e o teorema 6.73 nos mostra como podemos usá-las.
Teorema 6.73. SejamA eB duas matrizes estocásticas, e p um vetor estocástico tais que os produtosAB eAp são
bem definidos. EntãoAB também é uma matriz estocástica eAp é um vetor estocástico.
O teorema 6.74 nos dá a interpretação da multiplicação de uma matriz de transição por um vetor esto-
cástico.
Teorema 6.74. Seja T a matriz de transição de uma cadeia de Markov, e p um vetor estocástico representando uma
distribuição de probabilidades sobre os estados da cadeia. A matriz T , quando usada como operador linear em p, leva
à distribuição de probabilidades depois de um estágio.
Page 197
Ve
rs
ão
Pr
el
im
in
ar
Ál
ge
br
a
Li
ne
ar
- n
ot
as
de
au
la
–
ve
rs
ão
78
Je
rô
ni
m
o
C.
Pe
lle
gr
in
i
184 CAPÍTULO 6. AUTOVALORES, AUTOVETORES E DIAGONALIZAÇÃO
Demonstração. Seuponha que T seja estocástica nas colunas. A coluna j, portanto contém as probabilidades
de, estando no estado j, haver transição para cada um dos outros estados – ou seja, aij é a probabilidade
de haver transição para i quando o estado anterior era j. Então
Tp =
t11 t12 · · · t1n
t21 t22 t2n
...
. . .
tn1 tn2 tnn
p1
p2
...
pn
=
t11p1 + t21p2 + · · ·+ tn1pn
t12p1 + t22p2 + · · ·+ tn2pn
...
tn1p1 + tn2p2 + · · ·+ tnnpn
=
p1(t11 + t21 + · · ·+ tn1)
p2(t12 + t22 + · · ·+ tn2)
...
pn(t1n + t2n + · · ·+ tnn)
Se a matriz é estocástica nas linhas, pode-se repetir o argumento com o operador à direita, pT = p ′. �
Fica claro então que podemos aplciar a matriz de transição T iteradamente para obter a distribuição de
probabilidade sobre os estados após k estágios:
(T(T · · · T(Tp) · · · ))| {z }
k aplicações
= (TT · · · T)p = Tkp.
Teorema 6.75. Toda matriz estocástica tem um autovalor igual a um, e todos os outros autovalores são menores ou
iguais a um.
O vetor estocástico cuja existência o teorema 6.75 garante é chamado de distribuição estacionária.
De maneira geral, uma cadeia de Markov pode ter mais de uma distribuição estacionária
Exemplo 6.76. Se uma cadeia de Markov tem a matriz de transição(
1 0
0 1
)
,
verificamos facilmente que há dois autovalores iguais a um, e que seus autovetores são
(1, 0)T e (0, 1)T .
Assim, as duas distribuições estacionárias são
(
1
2
, 0
)T
e
(
0,
1
2
)T
. J
Page 391
Ve
rs
ão
Pr
el
im
in
ar
Ál
ge
br
a
Li
ne
ar
- n
ot
as
de
au
la
–
ve
rs
ão
78
Je
rô
ni
m
o
C.
Pe
lle
gr
in
i
378 ÍNDICE REMISSIVO
núcleo e imagem (teorema), 77
número algébrico, 7
número transcendental, 7
norma, 196
notação
de Einstein, 328
indicial, 328
nulidade, 77
operação, 2
binária, 2
operação elementar, 107
operador
idempotente, 207
operador linear, 63
nilpotente, 238
orientação, 135, 353
ortogonal
família de funções, 300
ortonormal
família de funções, 300
oscilador harmônico, 320
otimização, 277
otimização linear, 124
pagerank, 185
parábola, 263
parabolóide
elíptico, 267
hiperbólico, 267
paralelepípedo, 133
período, 293
permutação, 143
paridade de, 144
Pitágoras
teorema de, 201
pivô, 112, 333
plano complexo, 60
plano da imagem, 290
plano do objeto, 290
polinômio característico, 161
politopo, 125
ponto crítico, 275
ponto de fuga principal, 290
posto, 77
de matriz, 94
posto de colunas, 94
posto de linhas, 94
produto de Frobenius, 193
produto interno, 191
em espaços complexos, 217
produto tensorial, 329
programa quadrático, 277
projeção, 206
ortogonal em subespaço, 211
projeção ortogonal, 209
protocolo Diffie-Hellman, 29
pseudoinversa, 227
de matriz complexa, 229
quádrica, 262, 264
recorrência, 172
homogênea, 172
linear, 172
reflexão, 80
regra de Cramer, 146
regressão linear, 221
reticulado, 245
determinante de, 247
menor base, 248
menor vetor, 248
vetor mais próximo, 248
reticulados
criptossistemas baseados em, 253
rotação em R2, 64
série
erro em aproximação, 309
soma parcial, 309
série de funções, 308
convergência pontual, 312
convergência uniforme, 313
Sarrus (rega para cálculo de determinante), 141
SBP, 248
semidefinida
matriz, 258
separação de variáveis, 323
Sequência, 15
sequencia de funções, 308
similaridade, vejamatrizes similares
Simplex (algoritmo), 127
sistema de equações
diferenciais, 180
Page 392
Ve
rs
ão
Pr
el
im
in
ar
Ál
ge
br
a
Li
ne
ar
- n
ot
as
de
au
la
–
ve
rs
ão
78
Je
rô
ni
m
o
C.
Pe
lle
gr
in
i
ÍNDICE REMISSIVO 379
sistema de equações lineares, veja sistema linear
consistente, 332
determinado, 332
equivalente, 332
inconsistente, 332
indeterminado, 332
sistema linear, 109, 331
de inequações, 126
forma escalonada por linhas, 333
forma escalonada reduzida por linhas, 333
homogêneo, 331
homogêneo, soluções como subespaço, 24, 110
solução trivial, 110
sistema triangular
forma triangular, 333
solução básica (em otimização linear), 127
soma de matrizes, vejamatriz, soma de
soma de subespaços, 26
dimensão de, 50
direta, 27
soma direta, 27
subespaço, 20
invariante, 235
subespaço próprio, 160
SVP, 248
tensor, 261, 329
transformação
composição, 67
transformação afim, 285
transformação linear, 63
inversa, 69
translação, 81
transposta de matriz, vejamatriz transposta
vértice, 17
variância, 220
vetor
coluna, 336
derivada de, 180
estocástico, 183
integral de, 180
linha, 336
vetor característico
de subgrafo, 18
vetor mais próximo
problema em reticulados, 248
vetores ortogonais, 202
volume, 134
volume orientado, 133
votação (sistema), 346
Wronskiano, 150
1
Ælgebra linear
versão 78
28 de maio de 2014
jerônimo c. pellegrini
Page 196
Ve
rs
ão
Pr
el
im
in
ar
Ál
ge
br
a
Li
ne
ar
- n
ot
as
de
au
la
–
ve
rs
ão
78
Je
rô
ni
m
o
C.
Pe
lle
gr
in
i
6.6. APLICAÇÕES 183
Usaremos como exemplo a modelagem, extremamente simplificada, da evolução de uma doença. Su-
ponha que
Representamos o estado de um sistema em um processo estocástico como um vetor de estado. A evo-
lução do sistema é descrita por uma sequencia de vetores de estado, onde cada um pode depender, proba-
bilisticamente, dos anteriores.
Definição 6.66 (cadeia deMarkov). Se um sistema pode ser descrito em um dadomomento t por um vetor
de estados, e o estado no momento t+ 1 depende apenas do estado no momento t e de probabilidades de
transição entre estados, então a sequência de vetores de estado desse sistema é uma cadeia de Markov. �
Definição 6.67 (matriz de transição). Se, para cada par de estados i, j, a probabilidade de transição de i
para j é pij, então a matriz de transição da cadeia de Markov é dada por (pi,j), ou
P =
p11 p12 p13p21 p22 p23
p31 p32 p33
�
Exemplo 6.68. A matriz
P =
(
0.2 0.1 0.7
0.1 0.5 0.4
0.6 0.2 0.2
)
representa as probabilidades de transição em uma cadeia de Markov com tres estados. J
Um vetor estocástico é um vetor que representa uma distribuição de probabilidades.
Definição 6.69 (vetor estocástico). Um vetor v ∈ Rn é estocástico se P i vi = 1, e todos os vi são não-
negativos. �
Exemplo 6.70. Os vetores (1, 0, 0)T , (1/2, 1/2, 0)T e (1/4, 0, 3/4, 0)T são estocásticos. J
Definição 6.71 (matriz estocástica). Umamatriz é estocástica se todas as suas linhas ou todas as suas colu-
nas forem vetores estocásticos.
Se tanto as linhas como as colunas de uma matriz são vetors estocásticos, dizemos que a matriz é du-
plamente estocástica. �
Exemplo 6.72. Amatriz de transição de qualquer cadeia deMarkov é estocástica. Por exemplo, amatriz do
exemplo 6.68 é uma matriz estocástica, porque só tem entradas positivas e a soma de cada linha é um. J
As matrizes de transição são operadores lineares, e o teorema 6.73 nos mostra como podemos usá-las.
Teorema 6.73. SejamA eB duas matrizes estocásticas, e p um vetor estocástico tais que os produtosAB eAp são
bem definidos. EntãoAB também é uma matriz estocástica eAp é um vetor estocástico.
O teorema 6.74 nos dá a interpretação da multiplicação de uma matriz de transição por um vetor esto-
cástico.
Teorema 6.74. Seja T a matriz de transição de uma cadeia de Markov, e p um vetor estocástico representando uma
distribuição de probabilidades sobre os estados da cadeia. A matriz T , quando usada como operador linear em p, leva
à distribuição de probabilidades depois de um estágio.
Page 197
Ve
rs
ão
Pr
el
im
in
ar
Ál
ge
br
a
Li
ne
ar
- n
ot
as
de
au
la
–
ve
rs
ão
78
Je
rô
ni
m
o
C.
Pe
lle
gr
in
i
184 CAPÍTULO 6. AUTOVALORES, AUTOVETORES E DIAGONALIZAÇÃO
Demonstração. Seuponha que T seja estocástica nas colunas. A coluna j, portanto contém as probabilidades
de, estando no estado j, haver transição para cada um dos outros estados – ou seja, aij é a probabilidade
de haver transição para i quando o estado anterior era j. Então
Tp =
t11 t12 · · · t1n
t21 t22 t2n
...
. . .
tn1 tn2 tnn
p1
p2
...
pn
=
t11p1 + t21p2 + · · ·+ tn1pn
t12p1 + t22p2 + · · ·+ tn2pn
...
tn1p1 + tn2p2 + · · ·+ tnnpn
=
p1(t11 + t21 + · · ·+ tn1)
p2(t12 + t22 + · · ·+ tn2)
...
pn(t1n + t2n + · · ·+ tnn)
Se a matriz é estocástica nas linhas, pode-se repetir o argumento com o operador à direita, pT = p ′. �
Fica claro então que podemos aplciar a matriz de transição T iteradamente para obter a distribuição de
probabilidade sobre os estados após k estágios:
(T(T · · · T(Tp) · · · ))| {z }
k aplicações
= (TT · · · T)p = Tkp.
Teorema 6.75. Toda matriz estocástica tem um autovalor igual a um, e todos os outros autovalores são menores ou
iguais a um.
O vetor estocástico cuja existência o teorema 6.75 garante é chamado de distribuição estacionária.
De maneira geral, uma cadeia de Markov pode ter mais de uma distribuição estacionária
Exemplo 6.76. Se uma cadeia de Markov tem a matriz de transição(
1 0
0 1
)
,
verificamos facilmente que há dois autovalores iguais a um, e que seus autovetores são
(1, 0)T e (0, 1)T .
Assim, as duas distribuições estacionárias são
(
1
2
, 0
)T
e
(
0,
1
2
)T
. J
Page 391
Ve
rs
ão
Pr
el
im
in
ar
Ál
ge
br
a
Li
ne
ar
- n
ot
as
de
au
la
–
ve
rs
ão
78
Je
rô
ni
m
o
C.
Pe
lle
gr
in
i
378 ÍNDICE REMISSIVO
núcleo e imagem (teorema), 77
número algébrico, 7
número transcendental, 7
norma, 196
notação
de Einstein, 328
indicial, 328
nulidade, 77
operação, 2
binária, 2
operação elementar, 107
operador
idempotente, 207
operador linear, 63
nilpotente, 238
orientação, 135, 353
ortogonal
família de funções, 300
ortonormal
família de funções, 300
oscilador harmônico, 320
otimização, 277
otimização linear, 124
pagerank, 185
parábola, 263
parabolóide
elíptico, 267
hiperbólico, 267
paralelepípedo, 133
período, 293
permutação, 143
paridade de, 144
Pitágoras
teorema de, 201
pivô, 112, 333
plano complexo, 60
plano da imagem, 290
plano do objeto, 290
polinômio característico, 161
politopo, 125
ponto crítico, 275
ponto de fuga principal, 290
posto, 77
de matriz, 94
posto de colunas, 94
posto de linhas, 94
produto de Frobenius, 193
produto interno, 191
em espaços complexos, 217
produto tensorial, 329
programa quadrático, 277
projeção, 206
ortogonal em subespaço, 211
projeção ortogonal, 209
protocolo Diffie-Hellman, 29
pseudoinversa, 227
de matriz complexa, 229
quádrica, 262, 264
recorrência, 172
homogênea, 172
linear, 172
reflexão, 80
regra de Cramer, 146
regressão linear, 221
reticulado, 245
determinante de, 247
menor base, 248
menor vetor, 248
vetor mais próximo, 248
reticulados
criptossistemas baseados em, 253
rotação em R2, 64
série
erro em aproximação, 309
soma parcial, 309
série de funções, 308
convergência pontual, 312
convergência uniforme, 313
Sarrus (rega para cálculo de determinante), 141
SBP, 248
semidefinida
matriz, 258
separação de variáveis, 323
Sequência, 15
sequencia de funções, 308
similaridade, vejamatrizes similares
Simplex (algoritmo), 127
sistema de equações
diferenciais, 180
Page 392
Ve
rs
ão
Pr
el
im
in
ar
Ál
ge
br
a
Li
ne
ar
- n
ot
as
de
au
la
–
ve
rs
ão
78
Je
rô
ni
m
o
C.
Pe
lle
gr
in
i
ÍNDICE REMISSIVO 379
sistema de equações lineares, veja sistema linear
consistente, 332
determinado, 332
equivalente, 332
inconsistente, 332
indeterminado, 332
sistema linear, 109, 331
de inequações, 126
forma escalonada por linhas, 333
forma escalonada reduzida por linhas, 333
homogêneo, 331
homogêneo, soluções como subespaço, 24, 110
solução trivial, 110
sistema triangular
forma triangular, 333
solução básica (em otimização linear), 127
soma de matrizes, vejamatriz, soma de
soma de subespaços, 26
dimensão de, 50
direta, 27
soma direta, 27
subespaço, 20
invariante, 235
subespaço próprio, 160
SVP, 248
tensor, 261, 329
transformação
composição, 67
transformação afim, 285
transformação linear, 63
inversa, 69
translação, 81
transposta de matriz, vejamatriz transposta
vértice, 17
variância, 220
vetor
coluna, 336
derivada de, 180
estocástico, 183
integral de, 180
linha, 336
vetor característico
de subgrafo, 18
vetor mais próximo
problema em reticulados, 248
vetores ortogonais, 202
volume, 134
volume orientado, 133
votação (sistema), 346
Wronskiano, 150
