Matriz companheira

Na álgebra linear, a matriz companheira de Frobenius do polinômio mônico

p ( x ) =

x + ⋯ +

n − 1

{\displaystyle p(x)=c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}+x^{n}}

é a matriz quadrada definida como

C ( p ) =

[

...

−

...

−

...

−

⋮

⋱

⋮

...

−

n − 1

]

{\displaystyle C(p)={\begin{bmatrix}0&0&\dots &0&-c_{0}\\1&0&\dots &0&-c_{1}\\0&1&\dots &0&-c_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\dots &1&-c_{n-1}\end{bmatrix}}.}

Alguns autores usam a transposta desta matriz,

C ( p

)

{\displaystyle C(p)^{T}}

, que é mais conveniente para alguns propósitos, como em relações de recorrência lineares (veja abaixo).

C ( p )

{\displaystyle C(p)}

é definida a partir dos coeficientes de

p ( x )

{\displaystyle p(x)}

, enquanto o polinômio característico bem como o polinômio mínimo de

C ( p )

{\displaystyle C(p)}

são iguais a

p ( x )

{\displaystyle p(x)}

. Neste sentido, a matriz

C ( p )

{\displaystyle C(p)}

e o polinômio

p ( x )

{\displaystyle p(x)}

são "companheiros".

Semelhança com a matriz companheira Qualquer matriz A com entradas num corpo F possui polinômio característico

p ( x ) = det ( x I − A )

{\displaystyle p(x)=\det(xI-A)}

, que por sua vez possui a matriz companheira

C ( p )

{\displaystyle C(p)}

. Estas matrizes estão relacionadas da seguinte forma. As seguintes afirmações são equivalentes:

A é semelhante sobre F a

C ( p )

{\displaystyle C(p)}

, isto é, A pode ser conjugada com sua matriz companheira por matrizes em GLn(F); o polinômio característico

p ( x )

{\displaystyle p(x)}

coincide com o polinômio mínimo de A, isto é, o polinômio mínimo tem grau n; a transformação linear

A :

→

{\displaystyle A:F^{n}\to F^{n}}

faz de

{\displaystyle F^{n}}

F [ A ]

{\displaystyle F[A]}

-módulo cíclico, possuindo uma base da forma

{ v , A v , ... ,

n − 1

v }

{\displaystyle \{v,Av,\ldots ,A^{n-1}v\}}

; ou, de forma equivalente,

≅ F [ X ]

( p ( x ) )

{\displaystyle F^{n}\cong F[X]/(p(x))}

como

F [ A ]

{\displaystyle F[A]}

-módulos. Se as condições acima forem válidas, diz-se que A é uma matriz não derrogatória. Nem toda matriz quadrada é semelhante a uma matriz companheira, mas toda matriz quadrada é semelhante a uma matriz diagonal de blocos feita de matrizes companheiras. Se exigirmos também que o polinômio de cada bloco diagonal divida o seguinte, eles serão determinados de forma única por A, e isso fornece a forma canônica racional (ou forma normal de Frobenius) de A.

Diagonalização As raízes do polinômio característico

p ( x )

{\displaystyle p(x)}

são os autovalores de

C ( p )

{\displaystyle C(p)}

. Se houver n autovalores distintos

, ... ,

{\displaystyle \lambda _{1},\ldots ,\lambda _{n}}

, então

C ( p )

{\displaystyle C(p)}

é diagonalizável como

C ( p ) =

− 1

D V

{\displaystyle C(p)=V^{-1}\!DV}

, onde D é a matriz diagonal e V é a matriz de Vandermonde correspondente aos λs:

D =

[

⋯

⋮

⋱

⋮

⋯

]

V =

[

⋯

n − 1

⋯

n − 1

⋮

⋱

⋮

⋯

n − 1

]

{\displaystyle D={\begin{bmatrix}\lambda _{1}&0&\!\!\!\cdots \!\!\!&0\\0&\lambda _{2}&\!\!\!\cdots \!\!\!&0\\\vdots &\vdots &\!\!\!\ddots \!\!\!&\vdots \\0&0&\!\!\!\cdots \!\!\!&\lambda _{n}\end{bmatrix}},\qquad V={\begin{bmatrix}1&\lambda _{1}&\lambda _{1}^{2}&\!\!\!\cdots \!\!\!&\lambda _{1}^{n-1}\\1&\lambda _{2}&\lambda _{2}^{2}&\!\!\!\cdots \!\!\!&\lambda _{2}^{n-1}\\[-1em]\vdots &\vdots &\vdots &\!\!\!\ddots \!\!\!&\vdots \\1&\lambda _{n}&\lambda _{n}^{2}&\!\!\!\cdots \!\!\!&\lambda _{n}^{n-1}\end{bmatrix}}.}

De fato, um cálculo razoavelmente complexo mostra que a transposta

C ( p

)

{\displaystyle C(p)^{T}}

possui autovetores

= ( 1 ,

, ... ,

n − 1

)

{\displaystyle v_{i}=(1,\lambda _{i},\ldots ,\lambda _{i}^{n-1})}

com

C ( p

)

(

) =

{\displaystyle C(p)^{T}\!(v_{i})=\lambda _{i}v_{i}}

, o que decorre de

p (

) =

+ ⋯ +

n − 1

= 0

{\displaystyle p(\lambda _{i})=c_{0}+c_{1}\lambda _{i}+\cdots +c_{n-1}\lambda _{i}^{n-1}+\lambda _{i}^{n}=0}

. Assim, sua matriz de mudança de base diagonalizadora é

= [

...

]

{\displaystyle V^{T}=[v_{1}^{T}\ldots v_{n}^{T}]}

, o que significa que

C ( p

)

(

)

− 1

{\displaystyle C(p)^{T}=V^{T}D\,(V^{T})^{-1}}

. Tomando a transposta de ambos os lados obtemos

C ( p ) =

− 1

D V

{\displaystyle C(p)=V^{-1}\!DV}

. Podemos ler os autovetores de

C ( p )

{\displaystyle C(p)}

com

C ( p ) (

) =

{\displaystyle C(p)(w_{i})=\lambda _{i}w_{i}}

a partir da equação

C ( p ) =

− 1

D V

{\displaystyle C(p)=V^{-1}\!DV}

: eles são os vetores coluna da matriz de Vandermonde inversa

− 1

= [

⋯

]

{\displaystyle V^{-1}=[w_{1}^{T}\cdots w_{n}^{T}]}

. Esta matriz é conhecida explicitamente, fornecendo os autovetores

= (

0 i

, ... ,

( n − 1 ) i

)

{\displaystyle w_{i}=(L_{0i},\ldots ,L_{(n-1)i})}

, com coordenadas iguais aos coeficientes dos polinômios de Lagrange

( x ) =

0 i

1 i

x + ⋯ +

( n − 1 ) i

n − 1

∏

j ≠ i

x −

−

p ( x )

( x −

)

p ′

(

)

{\displaystyle L_{i}(x)=L_{0i}+L_{1i}x+\cdots +L_{(n-1)i}x^{n-1}=\prod _{j\neq i}{\frac {x-\lambda _{j}}{\lambda _{j}-\lambda _{i}}}={\frac {p(x)}{(x-\lambda _{i})\,p'(\lambda _{i})}}.}

Alternativamente, os autovetores escalonados

w ~

p ′

(

)

{\displaystyle {\tilde {w}}_{i}=p'\!(\lambda _{i})\,w_{i}}

possuem coeficientes mais simples. Se

p ( x )

{\displaystyle p(x)}

possuir raízes múltiplas, então

C ( p )

{\displaystyle C(p)}

não é diagonalizável. Em vez disso, a forma canônica de Jordan de

C ( p )

{\displaystyle C(p)}

contém um bloco de Jordan para cada raiz distinta; se a multiplicidade da raiz for m, então o bloco é uma matriz m × m com

{\displaystyle \lambda }

na diagonal e 1 nas entradas imediatamente acima da diagonal. Neste caso, V torna-se uma matriz de Vandermonde confluente.

Sequências recursivas lineares Uma sequência recursiva linear definida por

k + n

= −

−

k + 1

⋯ −

n − 1

k + n − 1

{\displaystyle a_{k+n}=-c_{0}a_{k}-c_{1}a_{k+1}\cdots -c_{n-1}a_{k+n-1}}

para

k ≥ 0

{\displaystyle k\geq 0}

tem o polinômio característico

p ( x ) =

x + ⋯ +

n − 1

{\displaystyle p(x)=c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}+x^{n}}

, cuja matriz companheira transposta

C ( p

)

{\displaystyle C(p)^{T}}

gera a sequência:

[

k + 1

k + 2

⋮

k + n − 1

k + n

]

[

⋯

⋮

⋱

⋮

⋯

−

⋯

−

n − 1

]

[

k + 1

⋮

k + n − 2

k + n − 1

]

{\displaystyle {\begin{bmatrix}a_{k+1}\\a_{k+2}\\\vdots \\a_{k+n-1}\\a_{k+n}\end{bmatrix}}={\begin{bmatrix}0&1&0&\cdots &0\\0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &1\\-c_{0}&-c_{1}&-c_{2}&\cdots &-c_{n-1}\end{bmatrix}}{\begin{bmatrix}a_{k}\\a_{k+1}\\\vdots \\a_{k+n-2}\\a_{k+n-1}\end{bmatrix}}.}

O vetor

v = ( 1 , λ ,

, ... ,

n − 1

)

{\displaystyle v=(1,\lambda ,\lambda ^{2},\ldots ,\lambda ^{n-1})}

é um autovetor desta matriz, onde o autovalor

{\displaystyle \lambda }

é uma raiz de

p ( x )

{\displaystyle p(x)}

. Definir os valores iniciais da sequência iguais a este vetor produz uma progressão geométrica

{\displaystyle a_{k}=\lambda ^{k}}

que satisfaz a recorrência. No caso de n autovalores distintos, uma solução arbitrária

{\displaystyle a_{k}}

pode ser escrita como uma combinação linear dessas soluções geométricas, e os autovalores de maior norma complexa fornecem uma aproximação assintótica.

De EDO linear para sistema de EDOs lineares de primeira ordem De forma semelhante ao caso acima de recursões lineares, considere uma EDO linear homogênea de ordem n para a função escalar

y = y ( t )

{\displaystyle y=y(t)}

( n )

n − 1

( n − 1 )

+ ⋯ +

( 1 )

y = 0.

{\displaystyle y^{(n)}+c_{n-1}y^{(n-1)}+\dots +c_{1}y^{(1)}+c_{0}y=0.}

Isto pode ser equivalentemente descrito como um sistema acoplado de EDOs lineares homogêneas de ordem 1 para a função vetorial

z ( t ) = ( y ( t ) ,

y ′

( t ) , ... ,

( n − 1 )

( t ) )

{\displaystyle z(t)=(y(t),y'(t),\ldots ,y^{(n-1)}(t))}

z ′

= C ( p

)

{\displaystyle z'=C(p)^{T}z}

onde

C ( p

)

{\displaystyle C(p)^{T}}

é a matriz companheira transposta para o polinômio característico

p ( x ) =

n − 1

+ ⋯ +

x +

{\displaystyle p(x)=x^{n}+c_{n-1}x^{n-1}+\cdots +c_{1}x+c_{0}.}

Aqui, os coeficientes

( t )

{\displaystyle c_{i}=c_{i}(t)}

também podem ser funções, não apenas constantes. Se

C ( p

)

{\displaystyle C(p)^{T}}

for diagonalizável, então uma mudança de base diagonalizadora transformará isso num sistema desacoplado equivalente a uma EDO linear homogênea de primeira ordem escalar em cada coordenada. Uma equação não homogênea

( n )

n − 1

( n − 1 )

+ ⋯ +

( 1 )

y = f ( t )

{\displaystyle y^{(n)}+c_{n-1}y^{(n-1)}+\dots +c_{1}y^{(1)}+c_{0}y=f(t)}

é equivalente ao sistema:

z ′

= C ( p

)

z + F ( t )

{\displaystyle z'=C(p)^{T}z+F(t)}

com o termo não homogêneo

F ( t ) = ( 0 , ... , 0 , f ( t ) )

{\displaystyle F(t)=(0,\ldots ,0,f(t))}

. Novamente, uma mudança de base diagonalizadora transformará isso num sistema desacoplado de EDOs lineares não homogêneas de primeira ordem escalares.

Matriz de deslocamento cíclico No caso de

p ( x ) =

− 1

{\displaystyle p(x)=x^{n}-1}

, quando os autovalores são as raízes da unidade complexas, a matriz companheira e sua transposta reduzem-se à matriz de deslocamento cíclico de Sylvester, uma matriz circulante.

Mapa de multiplicação em uma extensão de corpo simples Considere um polinômio

p ( x ) =

n − 1

+ ⋯ +

x +

{\displaystyle p(x)=x^{n}+c_{n-1}x^{n-1}+\cdots +c_{1}x+c_{0}}

com coeficientes em um corpo

{\displaystyle F}

, e suponha que

p ( x )

{\displaystyle p(x)}

seja irredutível no anel de polinômios

F [ x ]

{\displaystyle F[x]}

. Em seguida, a adjunção de uma raiz

{\displaystyle \lambda }

p ( x )

{\displaystyle p(x)}

produz uma extensão de corpo

K = F ( λ ) ≅ F [ x ]

( p ( x ) )

{\displaystyle K=F(\lambda )\cong F[x]/(p(x))}

, que também é um espaço vetorial sobre

{\displaystyle F}

com base padrão

{ 1 , λ ,

, ... ,

n − 1

}

{\displaystyle \{1,\lambda ,\lambda ^{2},\ldots ,\lambda ^{n-1}\}}

. Então o mapeamento de multiplicação linear sobre

{\displaystyle F}

tem uma matriz n × n

[

]

{\displaystyle [m_{\lambda }]}

com respeito à base padrão. Como

(

) =

i + 1

{\displaystyle m_{\lambda }(\lambda ^{i})=\lambda ^{i+1}}

(

n − 1

) =

= −

− ⋯ −

n − 1

{\displaystyle m_{\lambda }(\lambda ^{n-1})=\lambda ^{n}=-c_{0}-\cdots -c_{n-1}\lambda ^{n-1}}

, esta é a matriz companheira de

p ( x )

{\displaystyle p(x)}

[

] = C ( p ) .

{\displaystyle [m_{\lambda }]=C(p).}

Assumindo que esta extensão é separável (por exemplo, se

{\displaystyle F}

tem característica zero ou é um corpo finito),

p ( x )

{\displaystyle p(x)}

tem raízes distintas

, ... ,

{\displaystyle \lambda _{1},\ldots ,\lambda _{n}}

com

= λ

{\displaystyle \lambda _{1}=\lambda }

, de modo que

p ( x ) = ( x −

) ⋯ ( x −

) ,

{\displaystyle p(x)=(x-\lambda _{1})\cdots (x-\lambda _{n}),}

e tem o corpo de decomposição

L = F (

, ... ,

)

{\displaystyle L=F(\lambda _{1},\ldots ,\lambda _{n})}

. Agora

{\displaystyle m_{\lambda }}

não é diagonalizável sobre

{\displaystyle F}

; em vez disso, devemos estendê-lo para um mapa linear sobre

{\displaystyle L}

≅ L

⊗

{\displaystyle L^{n}\cong L\otimes _{F}K}

, um espaço vetorial sobre

{\displaystyle L}

com base padrão

{ 1

⊗

1 ,

⊗

λ ,

⊗

, ... , 1

⊗

n − 1

}

{\displaystyle \{1{\otimes }1,\,1{\otimes }\lambda ,\,1{\otimes }\lambda ^{2},\ldots ,1{\otimes }\lambda ^{n-1}\}}

, contendo os vetores

w = (

, ... ,

) =

⊗

1 + ⋯ +

⊗

n − 1

{\displaystyle w=(\beta _{1},\ldots ,\beta _{n})=\beta _{1}{\otimes }1+\cdots +\beta _{n}{\otimes }\lambda ^{n-1}}

. O mapeamento estendido é definido por

( β ⊗ α ) = β ⊗ ( λ α )

{\displaystyle m_{\lambda }(\beta \otimes \alpha )=\beta \otimes (\lambda \alpha )}

. A matriz

[

] = C ( p )

{\displaystyle [m_{\lambda }]=C(p)}

permanece inalterada, mas, como acima, ela pode ser diagonalizada por matrizes com entradas em

{\displaystyle L}

[

] = C ( p ) =

− 1

D V ,

{\displaystyle [m_{\lambda }]=C(p)=V^{-1}\!DV,}

para a matriz diagonal

D = diag ⁡ (

, ... ,

)

{\displaystyle D=\operatorname {diag} (\lambda _{1},\ldots ,\lambda _{n})}

e a matriz de Vandermonde V correspondente a

, ... ,

∈ L

{\displaystyle \lambda _{1},\ldots ,\lambda _{n}\in L}

. A fórmula explícita para os autovetores (os vetores coluna escalonados da matriz de Vandermonde inversa

− 1

{\displaystyle V^{-1}}

) pode ser escrita como:

w ~

0 i

⊗

1 +

1 i

⊗

λ + ⋯ +

( n − 1 ) i

⊗

n − 1

∏

j ≠ i

( 1

⊗

λ −

⊗

1 )

{\displaystyle {\tilde {w}}_{i}=\beta _{0i}{\otimes }1+\beta _{1i}{\otimes }\lambda +\cdots +\beta _{(n-1)i}{\otimes }\lambda ^{n-1}=\prod _{j\neq i}(1{\otimes }\lambda -\lambda _{j}{\otimes }1)}

onde

i j

∈ L

{\displaystyle \beta _{ij}\in L}

são os coeficientes do polinômio de Lagrange escalonado

p ( x )

x −

∏

j ≠ i

( x −

) =

0 i

1 i

x + ⋯ +

( n − 1 ) i

n − 1

{\displaystyle {\frac {p(x)}{x-\lambda _{i}}}=\prod _{j\neq i}(x-\lambda _{j})=\beta _{0i}+\beta _{1i}x+\cdots +\beta _{(n-1)i}x^{n-1}.}

Complexidade teórica: cálculo por multiplicação rápida de matrizes É possível calcular a matriz companheira de maneira rápida com o uso de algoritmos de multiplicação rápida de matrizes num tempo

O (

)

{\displaystyle O({n^{\omega }})}

para

2.37 ≤ ω < 3

{\displaystyle ~2.37\leq \omega <3}

. Os respectivos algoritmos são fornecidos por Storjohann.

Ver também Endomorfismo de Frobenius Teorema de Cayley-Hamilton Subespaço de Krylov

Referências

Matriz companheira

Mais conteúdos de Cultura

MC Cláudio

Phoenix (filme)