[PDF] Highly symmetric generalized circulant permutation matrices





Previous PDF Next PDF



Lightweight MDS Generalized Circulant Matrices (Full Version)

In short using a circulant matrix in the diffusion layer gives the observation leads us to generalize the circulant matrices to cyclic matrices



Double Circulant Matrices

2016. jan. 26. determine the rank r of a generalized circulant matrix and prove that any consecutive r rows of the matrix are linearly independent ...



A Generalization of Circulant Matrices for Non-Abelian Groups

1998. aug. 18. A circulant matrix of order n is the matrix of convolution by a fixed element of the group algebra of the cyclic group Zn. Replacing Zn by ...



Lightweight MDS Generalized Circulant Matrices

Lightweight MDS Generalized. Circulant Matrices. Meicheng Liu1? and Siang Meng Sim2



Generalized Inverses of Circulant and Generalized Circulant

For any matrix A there exists a unique matrix X which satisfies all four equations. This matrix X is called the Moore-Penrose inverse of A and is.



DETERMINANTAL PROPERTIES OF GENERALIZED CIRCULANT

2018. júl. 15. We call a circulant matrix C a generalized circulant Hadamard matrix ... Definition 1.3 extends the notion of circulant Hadamard matrices ...



Highly symmetric generalized circulant permutation matrices

2008. ápr. 11. In the same paper the following characterization of generalized h-circulant matrices is shown. Theorem 1.1. A matrix A of order n is generalized ...





The group inverse of some circulant matrices

general symmetric circulant and tridiagonal matrix is invertible and in this case



Linear Algebra and its Applications 429 (2008) 367-375Available online at www.sciencedirect.com www.elsevier.com/locate/laa Highly symmetric generalized circulant permutation matrices

M. Abreu

a , D. Labbate b , R. Salvi c , N. Zagaglia Salvic,? a

Dipartimento di Matematica, Università della Basilicata, C. da Macchia Romana, 85100 Potenza, Italy

b Dipartimento di Matematica, Politecnico di Bari, I-70125 Bari, Italy c

Dipartimento di Matematica, Politecnico di Milano, P.zza Leonardo da Vinci, 32, I-20133 Milano, Italy

Received 31 July 2006; accepted 26 February 2008

Available online 11 April 2008

Submitted by R.A. Brualdi

Abstract

in terms of circulant and retrocirculant block(0,1)-matrices in which each block contains exactly one or

two entries 1. In particular, we prove that a generalizedk-circulant matrixAof composite ordern=kmis symmetric if and only if eitherk=m-1ork≡0ork≡1 modm, and we obtain three basic symmetric

© 2008 Elsevier Inc. All rights reserved.Keywords:Generalized circulant matrix; Block circulant matrix; Centrosymmetric matrix; Persymmetric matrix

1. Introduction

A matrix of ordernis said to beh-circulant,1?hThis research was partially supported by M.I.U.R. (Ministero dell"Istruzione, dell"Università e della Ricerca).

Corresponding author.

E-mail addresses:abreu@unibas.it(M. Abreu),labbate@poliba.it(D. Labbate),rodolfo.salvi@polimi.it(R. Salvi),

norma.zagaglia@polimi.it(N. Zagaglia Salvi).

0024-3795/$ - see front matter

(2008 Elsevier Inc. All rights reserved.

doi:10.1016/j.laa.2008.02.033brought to you by COREView metadata, citation and similar papers at core.ac.ukprovided by Elsevier - Publisher Connector

368M. Abreu et al. / Linear Algebra and its Applications 429 (2008) 367-375

one by shifting every element 1 position to the left. LetP n be the circulant matrix having as first row(010...0). If there is no possibility of ambiguity we often drop the subscriptnand simply writeP n asP. In [3] a matrix A of ordern=kmand(n,h)=kis calledgeneralizedh-circulantwhen it is partitioned intoh-circulant submatrices of typem×n. LetA j ,1?j?k,betheh-circulant submatrix of A of typem×n, formed by the rows

1+(j-1)m,2+(j-1)m,...,jm;

thenAis partitioned inkblocks of typem×nas follows:? ??A 1 A 2 A k In the same paper the following characterization of generalizedh-circulant matrices is shown. Theorem 1.1.A matrix A of ordernis generalizedh-circulant,where(n,h)=kandn=km, if and only if it satisfies the relation AP h =P A, whereP is direct sum ofkmatrices coinciding withP m ,i.e.P =diag(P m ,...,P m A matrixAof ordern=km, partitioned intom×nsubmatricesA j ,1?j?k, is said to be(m×n)-block circulantwhen every block, different from the first one, is obtained from the preceding one by shifting every column one position to the right. This condition is equivalent to say thatA j+1 =A j

P, where 1?j?k-1.

The following is an example of a generalized 2-circulant matrix and a(2×4)-block circulant matrix both of order 4? ??1234 3412
5678
7856?
??and? ??1234 5678
4123
8567?
A matrixAof ordern, where(n,h)=kandn=km, is calledblock generalizedh-circulant if it is generalizedh-circulant and(m×n)-block circulant. An example of a block generalized 2-circulant matrix is? ??1234 3412
4123
2341?

A(0,1)-matrixA=[a

i,j ]is a permutation matrix if there exists a permutationσsuch that a i,j =1 if and only ifj=σ(i). If necessary, we useA(σ)to emphasizeσ. We will represent a permutation by the one-line notationσ=(σ(1)σ(2)...σ(n))[1]. Permutation matrices partitioned into particular submatrices are considered in [5]. Note that the circulant matrixP:=P n is always the permutation matrix asssociated to the permutation σ=(1...n). SincePis a permutation matrix, thenP T =P -1 ,P n =I n and(P T s-1 =P s whenn=2s-1. M. Abreu et al. / Linear Algebra and its Applications 429 (2008) 367-375369

3- or 5-circulant permutation matrices. Hence, it seems worthwhile to characterize the order and

the structure of symmetric generalizedk-circulant matrices of ordern=km. We present such a characterization in Section2. Furthermore, we extend such a characterization tocentrosymmetric matrices in Section3.

2. Symmetric matrices

LetAbe a generalizedk-circulant permutation matrix of composite ordern=km. LetA b [B i,j ]be the matrix obtained by partitioningAinto submatrices (blocks)B i,j of orderm. Recall that the matrixE i,j of orderndenotes the matrix having all the elements zero, buta1inposition (i,j). We will also consider thedistancebetween theith andjth rows (or columns) of a matrix A to be|i-j|.Consecutiverows (or columns) are those at distance 1. Also the first and last row (or column) of a matrix of ordermare consideredconsecutive modulo m.

TheithrowandithcolumnofA

b aredenotedbyR i =[B i,1 ,B i,2 ...B i,k ]andC i =[B 1,i ,B 2,i ...,B k,i T , with 1?i?k, respectively. The following is an immediate consequence of these definitions. Lemma 2.1.LetAbe a generalizedk-circulant permutation matrix.Then two ones ofR i belong i belong to rows having distance a multiple ofk.

We denote byP

b :=[P b i,j ]the block permutation(0,1)-matrix of orderkwith blocks of order msuch that P b i,j :=?I m ifj≡i+1 modk O m otherwise

Note:The matrixP

b has the same structure as the permutation matrixP k in which every entry

1 is substituted by the identity matrixI

m of orderm, and every entry 0 is substituted by the null matrixO m of orderm.

Theorem 2.2.LetA=[a

i,j n=km,with1···E i,m-i+1

···E

m-1,2 E m-1,2 E 1,m +E m,1

···E

i-1,m-i

···E

m-2,3 E 2,m-1 E 3,m-2

···E

m-1,2

···E

1,m +E m,1

Ifmis odd,saym=2s-1,wheres>1,A

b coincides either withK 1 or with the circulant block matrix K 2 ??E s,s E s+1,s+m-1

···E

1,m +E m,1

···E

s-1,s-m+1 E s-1,s-m+1 E s,s

···E

m-1,2

···E

s-2,s-m E s+1,s+m-1 E s+2,s-2

···E

2,m-1

···E

s,s

Moreover,K

2 :=K 1 P sb

370M. Abreu et al. / Linear Algebra and its Applications 429 (2008) 367-375

Proof.Note that thek-circulant submatrixR

1 =[B 1,1 ,B 1,2 ,...,B 1,k ], containsmones. Since k