Circulant matrix (original) (raw)
巡回行列（じゅんかいぎょうれつ）または循環行列（じゅんかんぎょうれつ、英: Circulant matrix）は、テプリッツ行列の特殊なものであり、各行ベクトルが1つ前の行ベクトルの要素を1つずらして配置した形になっているものである。数値解析において、巡回行列は離散フーリエ変換によって対角化されるため、それを含む線型方程式系は高速フーリエ変換で高速に解くことができる。
| Property | Value |
|---|---|
| dbo:abstract | In der linearen Algebra bezeichnet man eine Matrix als zyklisch oder zirkulant, wenn ihre Zeilen und Spalten eine bestimmte Permutationsbedingung erfüllen. Wegen des unten beschriebenen Zusammenhangs mit der diskreten schnellen Fourier-Transformation finden zyklische Matrizen Anwendung bei schnellen Lösungsverfahren z. B. für Toeplitz-Matrizen. Eine zirkulante Matrix ist eine spezielle Toeplitz-Matrix, bei der jeder Zeilenvektor relativ zum darüberliegenden Zeilenvektor um einen Eintrag nach rechts verschoben ist. Anders ausgedrückt ist sie ein Beispiel für ein Lateinisches Quadrat, wenn alle Zeilenelemente verschieden sind. Gleichungssysteme mit zirkulanten Matrizen können per diskreter Fourier-Transformation einfach gelöst werden. (de) In linear algebra, a circulant matrix is a square matrix in which all row vectors are composed of the same elements and each row vector is rotated one element to the right relative to the preceding row vector. It is a particular kind of Toeplitz matrix. In numerical analysis, circulant matrices are important because they are diagonalized by a discrete Fourier transform, and hence linear equations that contain them may be quickly solved using a fast Fourier transform. They can be as the integral kernel of a convolution operator on the cyclic group and hence frequently appear in formal descriptions of spatially invariant linear operations. This property is also critical in modern software defined radios, which utilize Orthogonal Frequency Division Multiplexing to spread the symbols (bits) using a cyclic prefix. This enables the channel to be represented by a circulant matrix, simplifying channel equalization in the frequency domain. In cryptography, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard. (en) En algèbre linéaire, une matrice circulante est une matrice carrée dans laquelle on passe d'une ligne à la suivante par permutation circulaire (décalage vers la droite) des coefficients. Une matrice circulante de taille n est donc de la forme où les coefficients ci sont des complexes. Une matrice circulante constitue un cas particulier de matrice de Toeplitz, de matrice de Frobenius (c'est la matrice générique de la multiplication par un élément de l'algèbre de groupe ℂ[ℤ/nℤ] et aussi un cas particulier de carré latin). La réduction des matrices circulantes fait intervenir les formules de la transformation de Fourier discrète.En analyse numérique, les systèmes circulants peuvent être résolus très efficacement par transformée de Fourier rapide. On parle parfois de matrice anticirculante ou circulante gauche quand on effectue un décalage à gauche des coefficients en passant d'une ligne à la suivante. (fr) 巡回行列（じゅんかいぎょうれつ）または循環行列（じゅんかんぎょうれつ、英: Circulant matrix）は、テプリッツ行列の特殊なものであり、各行ベクトルが1つ前の行ベクトルの要素を1つずらして配置した形になっているものである。数値解析において、巡回行列は離散フーリエ変換によって対角化されるため、それを含む線型方程式系は高速フーリエ変換で高速に解くことができる。 (ja) 선형 대수학에서 순환 행렬(circulant matrix)은 퇴플리츠 행렬의 특별한 종류이며 각 행 벡터는 선행 행 벡터에 비례하여 오른쪽으로 한 요소(성분)만큼 회전한다. 수치해석학에서 , 순환 행렬은 이산 푸리에 변환에 의해 대각화되기 때문에 중요하며, 따라서 이를 포함하는 선형 방정식은 고속 푸리에 변환을 사용하여 신속하게 해결 될 수 있다. 이들은 순환군 에서 컨볼루션 연산자의 완전한 커널로 분석적으로 해석 될 수 있다. 따라서 공간적으로 불변 인 선형 연산에 대한 공식적인 설명에 자주 등장한다. 암호화에서, 순환 행렬은 빈슨트 레이믄(Vincent Rijmen)과 요안 대믄(Joan Daemen)이 개발한 고급 암호화 표준(AES)인 (Rijndael MixColumns)단계에서 사용된다. (ko) Em matemática, uma matriz circulante é uma matriz quadrada em que cada linha i é formada por um deslocamento cíclico de i posições de uma mesma lista de elementos {a0,a1,a2 ... an-1}, ou seja que é um caso especial de matriz de Toeplitz. Toda matriz circulante é um quadrado latino. Uma definição alternativa e equaivalente a (1a) é onde mod é a função módulo e n é o número de linhas de A. (pt) Циркулянт или циркулянтная матрица — это матрица вида где все — комплексные числа. Циркулянт можно также кратко описать как . Таким образом, циркулянт — это матрица, в которой любая следующая строка (столбец), начиная с первой (с первого) получается циклической алфавитной перестановкой элементов предыдущей строки (столбца). Любая циркулянтная матрица по определению является тёплицевой. Также циркулянтом часто называют определитель такой матрицы. (ru) En cyklisk matris är en matris där varje rad (och kolonn) är en cyklisk skiftning av elementen i den föregående raden (kolonnen). Cykliska matriser är ett specialfall av Toeplitzmatriser. Cykliska matriser används i samband med diskret Fouriertransform och inom Advanced Encryption Standard. (sv) У лінійній алгебрі, циркулянт — особливий підвид матриць Тепліца, в якій кожен вектор-стовпчик являє собою попередній вектор стовпчик циклічно зсунутий на один елемент праворуч. У обчислювальній математиці, циклічні матриці важливі, бо воно діагоналізовні за допомогою дискретного перетворення Фур'є, тобто, лінійні рівняння, які містять їх можна розв'язати застосувавши швидке перетворення Фур'є. Їх можна інтерпретувати аналітично як інтегральне ядро згортки циклічної групи тому вони часто з'являються у формальних описах просторово інваріантних лінійних операцій. У криптографії, циклічні матриці використовуються в MixColumns етапі в Advanced Encryption Standard. (uk) 在线性代数中，循环矩阵是一种特殊形式的 Toeplitz矩阵，它的列向量的每个元素都是前一个列向量各元素依次右移一个位置得到的结果。由于可以用离散傅立叶变换快速解循环矩阵，所以在数值分析中有重要的应用。 (zh) |
| dbo:wikiPageExternalLink | https://github.com/MMesch/toeplitz_spectrum/blob/master/toeplitz_spectrum.ipynb http://www-ee.stanford.edu/~gray/toeplitz.pdf |
| dbo:wikiPageID | 889936 (xsd:integer) |
| dbo:wikiPageLength | 14772 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1093547711 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Root_of_unity dbr:Row_vector dbr:Monic_polynomial dbr:Convolution_operator dbr:Derivative dbr:Determinant dbr:Permutation_matrix dbr:Characteristic_polynomial dbr:Vector_space dbr:Degree_of_a_polynomial dbr:Integral_transform dbr:Complex_number dbr:Cryptography dbr:Operator_theory dbr:Circular_convolution dbr:Eigenvalue dbr:Eigenvector dbr:Eigenvectors dbr:Gaussian_elimination dbr:Graph_(discrete_mathematics) dbr:Möbius_ladder dbr:Linear_algebra dbr:Linear_equation dbr:Commutative_algebra dbr:Moore–Penrose_inverse dbr:Parity_(mathematics) dbc:Matrices dbr:Transpose dbr:Square_matrix dbr:Adjacency_matrix dbr:Advanced_Encryption_Standard dbr:Cyclic_group dbr:Cyclic_permutation dbr:Cyclic_prefix dbc:Determinants dbr:Field_(mathematics) dbr:Numerical_analysis dbr:Dimension_(vector_space) dbr:Directed_graph dbr:Fast_Fourier_transform dbr:Graph_theory dbr:Rank_(linear_algebra) dbr:Hermitian_matrix dbr:Isomorphic dbr:Prime_number dbc:Numerical_linear_algebra dbr:Bisymmetric_matrix dbr:Symbols dbr:Toeplitz_matrix dbr:Diagonalizable_matrix dbr:Discrete_Fourier_transform dbr:Automorphism_group dbr:Polynomial dbc:Latin_squares dbr:Circulant_graph dbr:Frequency_domain dbr:Group_ring dbr:Imaginary_unit dbr:Integer dbr:Integral_kernel dbr:Order_(group_theory) dbr:Set_(mathematics) dbr:Real_line dbr:Paley_graph dbr:Rijndael_MixColumns dbr:Orthogonal_Frequency_Division_Multiplexing |
| dbp:id | CirculantMatrix (en) |
| dbp:title | Circulant Matrix (en) |
| dbp:wikiPageUsesTemplate | dbt:Doi dbt:For dbt:MathWorld dbt:Reflist dbt:Short_description dbt:Numerical_linear_algebra dbt:Matrix_classes |
| dct:subject | dbc:Matrices dbc:Determinants dbc:Numerical_linear_algebra dbc:Latin_squares |
| rdf:type | yago:WikicatMatrices yago:Abstraction100002137 yago:Arrangement107938773 yago:Array107939382 yago:Cognition100023271 yago:CognitiveFactor105686481 yago:Determinant105692419 yago:Group100031264 yago:Matrix108267640 yago:PsychologicalFeature100023100 yago:WikicatDeterminants |
| rdfs:comment | 巡回行列（じゅんかいぎょうれつ）または循環行列（じゅんかんぎょうれつ、英: Circulant matrix）は、テプリッツ行列の特殊なものであり、各行ベクトルが1つ前の行ベクトルの要素を1つずらして配置した形になっているものである。数値解析において、巡回行列は離散フーリエ変換によって対角化されるため、それを含む線型方程式系は高速フーリエ変換で高速に解くことができる。 (ja) 선형 대수학에서 순환 행렬(circulant matrix)은 퇴플리츠 행렬의 특별한 종류이며 각 행 벡터는 선행 행 벡터에 비례하여 오른쪽으로 한 요소(성분)만큼 회전한다. 수치해석학에서 , 순환 행렬은 이산 푸리에 변환에 의해 대각화되기 때문에 중요하며, 따라서 이를 포함하는 선형 방정식은 고속 푸리에 변환을 사용하여 신속하게 해결 될 수 있다. 이들은 순환군 에서 컨볼루션 연산자의 완전한 커널로 분석적으로 해석 될 수 있다. 따라서 공간적으로 불변 인 선형 연산에 대한 공식적인 설명에 자주 등장한다. 암호화에서, 순환 행렬은 빈슨트 레이믄(Vincent Rijmen)과 요안 대믄(Joan Daemen)이 개발한 고급 암호화 표준(AES)인 (Rijndael MixColumns)단계에서 사용된다. (ko) Em matemática, uma matriz circulante é uma matriz quadrada em que cada linha i é formada por um deslocamento cíclico de i posições de uma mesma lista de elementos {a0,a1,a2 ... an-1}, ou seja que é um caso especial de matriz de Toeplitz. Toda matriz circulante é um quadrado latino. Uma definição alternativa e equaivalente a (1a) é onde mod é a função módulo e n é o número de linhas de A. (pt) Циркулянт или циркулянтная матрица — это матрица вида где все — комплексные числа. Циркулянт можно также кратко описать как . Таким образом, циркулянт — это матрица, в которой любая следующая строка (столбец), начиная с первой (с первого) получается циклической алфавитной перестановкой элементов предыдущей строки (столбца). Любая циркулянтная матрица по определению является тёплицевой. Также циркулянтом часто называют определитель такой матрицы. (ru) En cyklisk matris är en matris där varje rad (och kolonn) är en cyklisk skiftning av elementen i den föregående raden (kolonnen). Cykliska matriser är ett specialfall av Toeplitzmatriser. Cykliska matriser används i samband med diskret Fouriertransform och inom Advanced Encryption Standard. (sv) У лінійній алгебрі, циркулянт — особливий підвид матриць Тепліца, в якій кожен вектор-стовпчик являє собою попередній вектор стовпчик циклічно зсунутий на один елемент праворуч. У обчислювальній математиці, циклічні матриці важливі, бо воно діагоналізовні за допомогою дискретного перетворення Фур'є, тобто, лінійні рівняння, які містять їх можна розв'язати застосувавши швидке перетворення Фур'є. Їх можна інтерпретувати аналітично як інтегральне ядро згортки циклічної групи тому вони часто з'являються у формальних описах просторово інваріантних лінійних операцій. У криптографії, циклічні матриці використовуються в MixColumns етапі в Advanced Encryption Standard. (uk) 在线性代数中，循环矩阵是一种特殊形式的 Toeplitz矩阵，它的列向量的每个元素都是前一个列向量各元素依次右移一个位置得到的结果。由于可以用离散傅立叶变换快速解循环矩阵，所以在数值分析中有重要的应用。 (zh) In der linearen Algebra bezeichnet man eine Matrix als zyklisch oder zirkulant, wenn ihre Zeilen und Spalten eine bestimmte Permutationsbedingung erfüllen. Wegen des unten beschriebenen Zusammenhangs mit der diskreten schnellen Fourier-Transformation finden zyklische Matrizen Anwendung bei schnellen Lösungsverfahren z. B. für Toeplitz-Matrizen. (de) In linear algebra, a circulant matrix is a square matrix in which all row vectors are composed of the same elements and each row vector is rotated one element to the right relative to the preceding row vector. It is a particular kind of Toeplitz matrix. In cryptography, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard. (en) En algèbre linéaire, une matrice circulante est une matrice carrée dans laquelle on passe d'une ligne à la suivante par permutation circulaire (décalage vers la droite) des coefficients. Une matrice circulante de taille n est donc de la forme où les coefficients ci sont des complexes. Une matrice circulante constitue un cas particulier de matrice de Toeplitz, de matrice de Frobenius (c'est la matrice générique de la multiplication par un élément de l'algèbre de groupe ℂ[ℤ/nℤ] et aussi un cas particulier de carré latin). (fr) |
| rdfs:label | Zyklische Matrix (de) Circulant matrix (en) Matrice circulante (fr) 순환 행렬 (ko) 巡回行列 (ja) Matriz circulante (pt) Циркулянт (ru) Cyklisk matris (sv) 循环矩阵 (zh) Циркулянт (uk) |
| owl:sameAs | freebase:Circulant matrix yago-res:Circulant matrix wikidata:Circulant matrix dbpedia-de:Circulant matrix dbpedia-fr:Circulant matrix dbpedia-hu:Circulant matrix dbpedia-ja:Circulant matrix dbpedia-ko:Circulant matrix dbpedia-pt:Circulant matrix dbpedia-ru:Circulant matrix dbpedia-sl:Circulant matrix dbpedia-sv:Circulant matrix dbpedia-uk:Circulant matrix dbpedia-zh:Circulant matrix https://global.dbpedia.org/id/2Jqzf |
| prov:wasDerivedFrom | wikipedia-en:Circulant_matrix?oldid=1093547711&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Circulant_matrix |
| is dbo:wikiPageRedirects of | dbr:Circulant_matrices dbr:Circulant dbr:Circulant_determinant dbr:Anti-circulant_matrix |
| is dbo:wikiPageWikiLink of | dbr:Root_of_unity dbr:Ménage_problem dbr:Number_theoretic_Hilbert_transform dbr:Cyclotomic_fast_Fourier_transform dbr:Integral_transform dbr:List_of_named_matrices dbr:List_of_numerical_analysis_topics dbr:Companion_matrix dbr:Convolution dbr:Low-density_parity-check_code dbr:Midpoint_polygon dbr:Symmetric_matrix dbr:Williamson_conjecture dbr:Circular_convolution dbr:Generalizations_of_Pauli_matrices dbr:Generalized_Clifford_algebra dbr:Linear_congruential_generator dbr:Linear_time-invariant_system dbr:Stationary_process dbr:Competitive_Lotka–Volterra_equations dbr:Ideal_lattice dbr:Moore–Penrose_inverse dbr:Permanent_(mathematics) dbr:Circulant_matrices dbr:Affine_symmetric_group dbr:Diagonal_matrix dbr:Fast_Fourier_transform dbr:Fourier_transform_on_finite_groups dbr:Koide_formula dbr:Regular_representation dbr:Coding_theory_approaches_to_nucleic_acid_design dbr:Toeplitz_matrix dbr:Discrete_Fourier_transform dbr:Circulant_graph dbr:Paley_construction dbr:Outline_of_linear_algebra dbr:Rijndael_MixColumns dbr:Circulant dbr:Circulant_determinant dbr:Anti-circulant_matrix |
| is foaf:primaryTopic of | wikipedia-en:Circulant_matrix |