AP07_2-3.vp In [1], the authors study matrices of morphisms preserv- ing the family of words coding 3-interval exchange transfor- mations. It is well known [2–4] that matrices of morphisms preserving sturmian words (i.e. words coding 2-interval ex- change transformations with the maximal possible subword complexity) form the monoid � � � �M M M MEM E� � � � � � �� �� �2 2 2 21det , where E � � �� � �� 0 1 1 0 . The result of [1] states that in the case of 3-interval exchange transformations the matrices preserving words cod- ing these transformations and having the maximal possible subword complexity belong to the monoid � �M MEM E M� � � � ���3 3 1and det , where E � � � � � � � � � � � 0 1 1 1 0 1 1 1 0 . We say that a matrix fulfilling the first condition has the so-called MEME Property. Definition 1 Let M � ��3 3. M is said to have the MEME Property if MEM ET � � , where E � � � � � � � � � � � 0 1 1 1 0 1 1 1 0 . The aim of this paper is to provide a stand-alone result connected with this property. Strictly speaking, we prove another algebraic characterization of matrices having this property. Before we give the above mentioned characterization, we need to prove the following technical lemma. Lemma 2 Let M � ��3 3, M � � �( ) ,mij i j1 3 be a matrix. Then M has the MEME Property if and only if there exists � �� � �1 1, such that det 1 1 1 21 22 23 31 32 33 � � � � � � � � �m m m m m m � , (1) det m m m m m m 11 12 13 31 32 32 1 1 1� � � � � � � � � � � , (2) det m m m m m m 11 12 13 21 22 23 1 1 1� � � � � � � � � � . (3) Proof. Let us denote K MEM� T . The transpose of K is K M E M KT T� � � �( ) and hence K is an anti-symmetric ma- trix. To investigate equalities of anti-symmetric matrices it suffices to consider elements k12, k13, k23. Let us compute these relevant elements of K. K k k k k k k m m m T� � � � � � � � � � � � � 0 0 0 12 13 12 23 13 23 11 12 1 MEM 3 21 22 23 31 32 33 0 1 1 1 0 1 1 1 0 m m m m m m � � � � � � � � � � � � � � � � � � � � � � � � � � � m m m m m m m m m m m m 11 21 31 12 22 32 13 23 33 12 13 11 � � � � � � � � � m m m m m m m m m m m m m m 13 11 12 22 23 21 23 21 22 32 33 32 33 31 32 11 21 31 12 22 32 13 23 33� � � � � � � � � � � � � m m m m m m m m m m � � , and hence k m m m m m m m m m k 12 12 13 21 11 13 22 11 12 23 13 � � � � � � � � � ( ) ( ) ( ) , ( m m m m m m m m m k m m 12 13 31 11 13 32 11 12 33 23 22 2 � � � � � � � � ) ( ) ( ) , ( 3 31 21 23 32 21 22 33) ( ) ( ) .m m m m m m m� � � � By definition of the determinant, k12 is equal to the left-hand side of (1), �k13 is equal to the left-hand side of (2), and k23 is equal to the left-hand side of (3). This implies K E� � if and only if equations (1)–(3) hold. � Now we can prove the two main theorems – one providing the desired characterization in the regular case and the other in the singular case. 68 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 47 No. 2–3/2007 Matrices Associated to 3-Interval Exchange Transformation and their Spectra P. Ambrož A three by three integer matrix M is said to have the MEME Property if MEM ET � � , where E � � � � � � � � � � � 0 1 1 1 0 1 1 1 0 . We characterize such matrices in terms of their spectra. Keywords: integer matrix, MEME Property, spectrum. Theorem 3 Let M � ��3 3 be a regular matrix. Then M has MEME if and only if the number det M or � det M is an eigenvalue of M with (1, �1, 1) being an associated left eigenvector. Proof. �: Denote �: det� M and let ��, � �� � �1 1, be an eigenvalue of M. If (1, �1, 1) is a left eigenvector of M associ- ated to � then we have the following dependence between rows of M, denoted by M M M1 2 3� � �, , ( , , ) ( , , )1 1 1 1 1 11 2 3� � � � � �� � �M M M M �� . (4) Using (4) we have � �� � � � � � � � � � � � � � � � � �det det ( , , ) M M M M M M M 1 2 3 1 1 3 1 1 1� 3� � � � � � � � , by subtracting the first and the third row from the second row and by factoring �� out from the second row we obtain � �� � � � � � � � � � � � � det ( , , ) M M 1 3 1 1 1 , which gives (2). Similarly, using the row dependence (4) in the first and in the third row of M provides the equalities (1) and (3). Therefore by Lemma 2 the matrix M has MEME. �: Let MT x x x 1 2 3 1 1 1 � � � � � � � � � � � � � � � � . (5) We will compute the components x1, x2, x3 using Cramer’s rule. x m m m m m m T1 21 31 22 32 23 33 1 1 1 1 � � � � � � � � � � det det det ( , M � � � � � � � � � � � 1 1 2 3 , ) det det M M M M � , where the last equality comes by Lemma 2 from the fact that M has MEME. Similarly, one can compute x2 � � � det M and x3 � � det M . Hence x x x 1 2 3 1 1 1 � � � � � � � � � � � � � � � � � det M . (6) Substituting (6) in (5) and multiplying by �det M , which is non-zero due to the regularity of M, we obtain ( , , ) det ( , , )1 1 1 1 1 1� � �M M� , that is, � det M is an eigenvalue of M, ( , , )1 1 1� is an associated left eigenvector. � Theorem 4. Let M � ��3 3 be a singular matrix. Then M has MEME if and only if � �� � � � �( ) , , ,M � � �0 12 3 2 3 and ( , , )1 1 1� is a left eigen- vector associated with the eigenvalue 0. Proof. �: Since det M � 0 we have 0 � � ( )M . Let x be a left eigenvector of M to the eigenvalue 0, i.e. xM � 0 and hence x x TE MEM� � 0, that is, x is also a left eigenvector of E, asso- ciated to 0. Obviously, x � �( , , )1 1 1 . Concerning the other eigenvalues of M, since the equality (4) for a singular M has the following form ( , , )1 1 1 01 2 3� � � � �� � �M M M M (7) the characteristic polynomial � �M( ) will be given by the matrix ( )M I� � � � � � �� � � m m m m m m m m m m m m 11 12 13 11 31 12 32 13 33 31 32 33 � � � � � � � �� . Computing its determinant, the linear component of � �M( ) is � � � � � � � � � � � � m m m m m m m m m m m m 33 12 11 33 11 32 13 32 13 31 12 31, which is exactly the left hand side of (2), and hence it is equal to �1. On the other hand, since the characteristic polynomial can be written in the form � � � � � � � � � � � � � � � � � M( ) ( )( )( ) ( ) ( � � � � � � � � � � 1 2 3 3 1 2 3 2 1 2 2 3 1 3 1 2 3� �� � � � �) ,x and, moreover, �1 0� �det M , the linear component of � �M( ) is also equal to ( )� �2 3 x . This implies � �2 3 1� � . �: Due to the row dependency (7) we have for the left hand side of (1) det det 1 1 1 1 1 1 21 22 23 31 32 33 11 31 � � � � � � � � � � � m m m m m m m m m m m m m m m m m m 12 32 13 33 31 32 33 11 12 13 1 1 1 � � � � � � � � � � � det m m m m m m m m m31 32 33 11 12 13 31 32 33 1 1 1 � � � � � � � � � � � �det � � � � � , and similarly for (3) det det m m m m m m m m m m 11 12 13 21 22 23 11 12 13 1 1 1 1� � � � � � � � � 1 31 12 32 13 33 11 12 13 31 1 1 1 � � � � � � � � � � � � m m m m m m m m m mdet 32 33 11 12 13 31 32 331 1 1 1 1 1m m m m m m m� � � � � � � � � � � � �det � � � � � . Therefore the conditions (1)–(3) are equivalent for singu- lar matrices. Using the same argument concerning the linear compo- nent of � �M( ) as in the previous part of the proof one can show that the conditions � �� � � � �( ) , , ,M � � �0 12 3 2 3and imply the equality (2) and hence M has MEME. � In addition to the above stated algebraic characterizations of matrices having the MEME property, there is also a nice re- lation between the singular and the non-singular case. Let © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 69 Acta Polytechnica Vol. 47 No. 2–3/2007 M � ��3 3 be a singular matrix having MEME and let us con- sider a matrix M, given by M M: ,� � � � � � � � � � � k 0 0 0 1 D 1 1 0 0 0 � ��� ��� where k � �. Since DE ED� �T 0 , we have MEM M D E M D MEM DEM MED DED MEM T T T T T T T T k k k k k � � � � � � � � � � ( ) ( ) E , hence also the regular matrix M has MEME. Equivalently, one can say that for each singular matrix M having MEME there exists a regular matrix M having MEME such that their first and third row coincide, that is, M M� � � � � � � � 1 0 0 1 0 1 0 0 1 . Acknowledgment The author acknowledges financial support from the Grant Agency of the Czech Republic GAČR 201/05/0169, and from Ministry of Education, Youth, and Sports of the Czech Republic grant LC 06002. References [1] Ambrož, P., Masáková, Z., Pelantová, E.: Matrices of 3iet Preserving Morphisms. Submitted to Theor. Comp. Sci., 2007. [2] Berstel, J., Séébold, P.: Morphismes de Sturm. Bull. Belg. Math. Soc. Simon Stevin, Vol. 1 (1994), p. 175–189. [3] Mignosi, F., Séébold, P.: Morphismes sturmiens et r gles de Rauzy. J. Théor. Nombres Bordeaux, Vol. 5 (1993), p. 221–233. [4] Séébold, P.: Fibonacci Morphisms and Sturmian Words. Theoret. Comput. Sci., Vol. 88 (1991), p. 365–384. Ing. Petr Ambrož, Ph.D. petr.ambroz@fjfi.cvut.cz Department of Mathematics Faculty of Nuclear Sciences and Physical Engineering Trojanova 13 120 00 Praha 2, Czech Republic 70 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 47 No. 2–3/2007