Dairesel matris

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Doğrusal cebirde, bir dairesel matris her satır vektörü önceki satır vektörüne doğru göreceli bir elemanın döndürüldüğü Toeplitz matrisinin özel bir türüdür.Bir ayrık Fourier dönüşümü ile kösegenlestirilir çünkü sayısal analizde, dairesel matrisler önemlidir,ve dolayısıyla bunları içeren doğrusal denklemler hızlı bir hızlı Fourier dönüşümü kullanarak çözülmüş olabilir.[1] Onlar siklik grup \mathbf{Z}/n\mathbf{Z} üzerinde bir evrişim operatörünün İntegral çekirdeği analitik yorumlanabilir.Kriptografide,dairesel matris gelişmiş şifreleme standardında katışık sütunlar içinde kullanılabilir.

Tanım[değiştir | kaynağı değiştir]

Bir n\times n dairesel matrisin \ C alınan formu


C=
\begin{bmatrix}
c_0     & c_{n-1} & \dots  & c_{2} & c_{1}  \\
c_{1} & c_0    & c_{n-1} &         & c_{2}  \\
\vdots  & c_{1}& c_0    & \ddots  & \vdots   \\
c_{n-2}  &        & \ddots & \ddots  & c_{n-1}   \\
c_{n-1}  & c_{n-2} & \dots  & c_{1} & c_0 \\
\end{bmatrix}.

Bir dairesel matris bir vektör \ c tarafından tamamen özeldir,bu \ C nin ilk sütunu olarak görünür,\ C nin kalan sütunları ile bir \ c vektörünün sütun indisine eşit dengeli her halkalı permutasyonudür.\ C nin son satırı \ c içinde tersten vektördür,ve geri kalan satırları son satırın her halkalı permutasyonudur.Farklı kaynaklardan katsayılar, birinci satır yerine matrisin ilk sütun karşılık gelen ya da kaymanın farklı bir yönü ile, örneğin, farklı şekillerde de dairesel matris tanımlar unutmayın.

Polinom  f(x) = c_0 + c_1 x + \dots + c_{n-1} x^{n-1} matris  C nin ilişkili polinomu olarak adlandırılır.

Özellikler[değiştir | kaynağı değiştir]

Özvektörler ve özdeğerler[değiştir | kaynağı değiştir]

Bir dairesel matrisin özvektörü aşağıdaki ile verilir

v_j=(1,~ \omega_j,~ \omega_j^2,~ \ldots,~ \omega_j^{n-1})^T,\quad j=0, 1,\ldots, n-1,

burada \omega_j=\exp \left(\tfrac{2\pi i j}{n}\right) n-inci birimin kökleri ve i=\sqrt{-1} sanal birim'dir.

Özdeğerlerin karşılığı ise şöyle verilir

\lambda_j = c_0+c_{n-1} \omega_j + c_{n-2} \omega_j^2 + \ldots + c_{1} \omega_j^{n-1}, \qquad j=0\ldots n-1.

Determinant[değiştir | kaynağı değiştir]

Yukardaki özdeğer için açık formülün bir sonucu olarak, dairesel matrisin determinantı şöyle hesaplanabilir:


\mathrm{det}(C) 
= \prod_{j=0}^{n-1} (c_0 + c_{n-1} \omega_j + c_{n-2} \omega_j^2 + \dots + c_1\omega_j^{n-1}).

bir matrisin özdeğeri devrik matrisle değiştirilemiyorsa, bir eşdeğer formulasyon;


\mathrm{det}(C)=\prod_{j=0}^{n-1} (c_0 + c_1 \omega_j + c_2 \omega_j^2 + \dots + c_{n-1}\omega_j^{n-1}) = \prod_{j=0}^{n-1} f(\omega_j).

Rank[değiştir | kaynağı değiştir]

Dairesel  C matrisinin rankı  n - d ye eşittir, burada  d ifadesi  \gcd( f(x), x^n - 1) in derecesidir.[2]

Diğer özellikler[değiştir | kaynağı değiştir]

  • Elimizde
 C=c_0I+c_{1}P+c_{2}P^2+\ldots+c_{n-1}P^{n-1}=f(P). var
burada P is the 'döngüsel permütasyon' matrisidir, bir özel permütasyon matrisi şöyle verilir
P=
\begin{bmatrix}
 0&0&\ldots&0&1\\
 1&0&\ldots&0&0\\
 0&\ddots&\ddots&\vdots&\vdots\\
 \vdots&\ddots&\ddots&0&0\\
 0&\ldots&0&1&0
\end{bmatrix}.
  • Dairesel matrisin bir değişmeli cebir formu ,nedeniyle verilen herhangi iki dairesel matrisin \ A and \ B,toplamı \ A + B daireseldir, çarpımı \ AB daireseldir, ve \ AB = BA.
 U_n = \frac{1}{\sqrt{n}} F_n, \quad\text{burada}\quad F_n = (f_{jk}) \quad\text{ile}\quad f_{jk} = \mathrm{e}^{-2jk\pi\mathrm{i}/n},  \quad\text{için}\quad  0\leq j,k<n.
Böylece, U_n matris C ile köşegenleştirilmiştir,aslında elimizde
 C = U_n^{*} \operatorname{diag}(F_n c) U_n = \frac{1}{n} F_n^{*} \operatorname{diag}(F_n c) F_n,

var

burada c\!\, ifadesi C\,\!nin ilk sütunudur. Böylece,C nin özdeğeri\ F_n c çarpımı ile verilir.Bu çarpım bir Hızlı Fourier dönüşümü tarafından kolayca hesaplanabilir .[3]

Analitik yorumlama[değiştir | kaynağı değiştir]

Ayrık Fourier dönüşümü ile bağlantısı açıklanarak,dairesel matrisler geometrik olarak yorumlanabilir

\mathbf{R}^n içinde düşünülen vektörler as fonksiyonlar olarak tamsayılar ile periyodu n, (yani periyodik çift-sonsuz dizisi olarak: \dots,a_0,a_1,\dots,a_{n-1},a_0,a_1,\dots) veya eşdeğerliliği,fonksiyon olarak n,sıranın döngüsel grubudur (C_n veya \mathbf{Z}/n\mathbf{Z}) geometrikseldir,(köşelerin) düzgün n-gon olarak:bu periyodik fonksiyonlara bir ayrık analog olarak gerçek çizgi ya da dairedir.

Eğer öyleyse, operator teorisinin bakışından, bir dairesel matris bir ayrık integral dönüşümünün çekirdeğidir, yani (c_0,c_1,\dots,c_{n-1}) fonksiyonunun evrişim operatörü için; bu bir ayrık dairesel evrişimdir.Formül için (b_i) := (c_i) * (a_i) fonksiyonunun evrişimi

b_k = \sum_{i=0}^{n-1} a_i c_{k-i} (yerine konan periyodiktir)

dairesel matris ile a_i vektörünün çarpımıdır . Ayrık Fourier dönüşümünde ise dönüştürülen evrişim çarpmadadır,matris penceresinde köşegenleştirmeye karşı gelir.

Uygulamalar[değiştir | kaynağı değiştir]

Doğrusal denklemlerde[değiştir | kaynağı değiştir]

Verilen bir matris denklemi

\ \mathbf{C} \mathbf{x} = \mathbf{b},

Burada \ C bir dairesel kare matris \ n in boyutunu dairesel evrişim denklemi olarak yazabiliriz

\ \mathbf{c} \star \mathbf{x} = \mathbf{b},

Burada \ c ifadesi \ C nin ilk sütunudur, ve \ c vektörleri, \ x ve \ b her yön içinde döngüsel genişletilmiştir.dairesel evrişim teoreminin sonuçları kullanılıyor, akıllı-eklenti çarpımı içinde dairesel evrişim dönüşümüne ayrık Fourier dönüşümü kullanabiliriz

\ \mathcal{F}_{n}(\mathbf{c} \star \mathbf{x}) = \mathcal{F}_{n}(\mathbf{c}) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})

böylece

\ \mathbf{x} = \mathcal{F}_{n}^{-1} 
\left [ 
\left (
\frac{(\mathcal{F}_n(\mathbf{b}))_{\nu}}
{(\mathcal{F}_n(\mathbf{c}))_{\nu}} 
\right )_{\nu \in \mathbf{Z}}
\right ]^T.

Bu algoritma özellikle eğer bir hızlı Fourier dönüşümü kullanılıyorsa çok daha hızlı standard Gauss elemesidir,.

Çizge kuramında[değiştir | kaynağı değiştir]

Çizge kuramında graf ya da digrafın komşuluk matrisi daireseldir dairesel graf (veya digraf) denir.Onun otomorfizm grubu, tam uzunlukta döngü içeriyorsa eşdeğeri bir graftır daireseldir.Möbiüs merdiveni dairesel graflara örnekleridir,yanı sıra asal düzenin alanları için Paley grafları vardır

Kaynakça[değiştir | kaynağı değiştir]

  1. ^ Davis, Philip J., Circulant Matrices, Wiley, New York, 1970 ISBN 0471057711
  2. ^ A. W. Ingleton (1956). "The Rank of Circulant Matrices". J. London Math. Soc. s1-31 (4): 445-460. doi:10.1112/jlms/s1-31.4.445. 
  3. ^ Golub, Gene H.; Van Loan, Charles F. (1996), "§4.7.7 Circulant Systems", Matrix Computations (3rd bas.), Johns Hopkins, ISBN 978-0-8018-5414-9 

Dış bağlantılar[değiştir | kaynağı değiştir]

Şablon:Numerical linear algebra