Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have an invertible rational matrix $C\in\text{GL}(n,\mathbb{Q})$ which works on lattice $\mathbb{Z}^{n}$. Can I write the resulting set in the following form $$C\cdot \mathbb{Z}^{n}=X\cdot \mathbb{Z}^{n}+\{U,V,\ldots\}$$ where $X$ a diagonal matrix with rational coefficients and $U,V,\ldots \in\mathbb{Q}^{n}$? The reasoning below tells me you can, but I can't find an expression for $X,U,V,\ldots$:

  1. For each $i\in\{1,\ldots n\}$ we can write $$C_{i1}\mathbb{Z}+\ldots+C_{in}\mathbb{Z}=\frac{1}{m}(a_{1}\mathbb{Z}+\ldots+a_{n}\mathbb{Z})$$ where $a_{1},\ldots,a_{n}\in\mathbb{Z}$ and $m=\text{LCD}(C_{i1},\ldots,C_{in})$ the least common denominator. ($C_{i*}$ is the i'th row of $C$)

  2. Using Bézout's identity this can be written as $$a_{1}\mathbb{Z}+\ldots+a_{n}\mathbb{Z}=x\mathbb{Z}$$ where $x=\text{GCD}(a_{1},\ldots,a_{n})$ the greatest common divisor.

  3. Finally we find that $$C_{i1}\mathbb{Z}+\ldots+C_{in}\mathbb{Z}=\frac{x}{m}\mathbb{Z}=x\mathbb{Z}+\{0,\frac{x}{m},\ldots,\frac{(m-1)x}{m}\}$$

Do this for all $i$ and make all possible combinations of the resulting sets and one would find an expression for $C\cdot \mathbb{Z}^{n}$ as given above. However one can not do (1-3) for all i independently. Therefore the resulting set should be stricter and the above reasoning should be done in dimension n:

  1. Analogue to (1) above but not for each row separately $$C\cdot \mathbb{Z}^{n}=\frac{1}{m}(A_{*1}\mathbb{Z}+\ldots+A_{*n}\mathbb{Z})$$ where $m$ the least common denominator of $C$ and $A_{*j}$ the columns of integer matrix $A$

  2. Analogue to (2): higher dimensional analogue to Bézout's identity? $$A_{*1}\mathbb{Z}+\ldots+A_{*n}\mathbb{Z}=?\quad X'\cdot \mathbb{Z}^{n}+\{U',V',\ldots\}$$ where $X'$ diagonal.

share|improve this question
    
Sorry but in $C\mathbb{Z}^n=X\mathbb{Z}+\{U, V,\ldots\}$ you have a lattice of dimension $n$ on the right and something (maybe a lattice) of dimension $1$ on the left. How can they be equal? –  wisefool Jan 8 '13 at 15:53
    
You're right, I corrected it. The expression is suggested by (3) for each component (although the components are not independent, which causes the problem I'm trying to solve). –  Wox Jan 8 '13 at 16:00
1  
Sorry, but again it doesn't make sense: $X^T\mathbb{Z}^n$ is a $1-$dimensional lattice, once again. The only thing you can put on the right is a matrix. Maybe you can write $C\mathbb{Z}^n=A\mathbb{Z}^n + \{b_j\}$ with $A$ made of integers and $b_j$ being the vectors of $c^{-1}\mathbb{Z}^n$ with all the entries with modulus less than $1$, $c$ being the lcd of the entries of $C$. But i'm not sure you would need exactly those $b_j$ ... –  wisefool Jan 8 '13 at 17:02
    
Sorry, I messed up. What I wanted to express was $(x_{1}\mathbb{Z},x_{2}\mathbb{Z},x_{3}\mathbb{Z})^{T}$. So if $X$ is $n\times n$ diagonal, that should do it. –  Wox Jan 8 '13 at 17:29
    
$C\mathbb{Z}^n=A\mathbb{Z}^n + \{b_j\}$ looks promising but I don't see how you can write this. For $n=1$ and $C=\frac{a}{m}$ ($a,m\in\mathbb{Z}$) we have $C\mathbb{Z}=a\mathbb{Z}+\{0,\frac{a}{m}+\ldots+\frac{a(m-1)}{m}\}$. –  Wox Jan 8 '13 at 17:43
show 3 more comments

1 Answer

up vote 3 down vote accepted

This is too long to be a comment. But I want to start a dialogue as to why you want to do this, and what you hope to achieve with this, so I type it as an answer instead. If this is totally off, just say so, and I will delete.

I am getting a vibe that you want to get good control of the free abelian group $C\cdot \mathbb{Z}^n$. More precisely, I cannot shake the feeling that the Smith normal form of an integer matrix might prove to be helpful to you. In this case it would give you the following. Let $m$ be the smallest positive integer such that $mC$ has integer entries. Smith normal form tells you that there exist matrices $U,V\in GL_n(\mathbb{Z})$ (i.e. matrices with integer entries such that the inverses of these matrices also have integer entries) such that $$ mC=U\pmatrix{d_1&0&0&\cdots&0\cr0&d_2&0&\cdots&0\cr0&0&d_3&\cdots&0\cr \vdots&\vdots&\vdots&\ddots&\vdots\cr0&0&0&\cdots&d_n}V, $$ where the integer of the diagonal are the invariant factors and can be arranged to satisfy the divisibility criteria $d_1\mid d_2\mid d_3\cdots\mid d_n$.

Because $V^{-1}$ also has integer entries, we have $V\cdot\mathbb{Z}^n=\mathbb{Z}^n$. Dividing the above equation by $m$ gives us thus $$ C\cdot \mathbb{Z}^n=U\pmatrix{d_1/m&0&0&\cdots&0\cr0&d_2/m&0&\cdots&0\cr0&0&d_3/m&\cdots&0\cr \vdots&\vdots&\vdots&\ddots&\vdots\cr0&0&0&\cdots&d_n/m}\mathbb{Z}^n. $$

In other words, we get something resembling what you wanted. On the plus side you don't have that messy set of fractional parts in the end. On the minus side you have that extra matrix $U$ sitting there in front of the desired diagonal matrix with rational entries. I don't see a way of getting rid of that $U$ factor in the general case. It may not be needed, if $C$ is of some special form, but I don't think that is very likely. You could absorb that $U$ to the matrix $C$ (multiply the last equation by $U^{-1}$ from the left), or you could state that the possible "fractional parts" of the vectors in $C\mathbb{Z}^n$ are all the integral linear combinations of the columns of $U$ multiplied by $d_i/m$ (use that factor with the $i^{th}$ column of $U$).

Does this look at all like what you need?

share|improve this answer
    
+1 for suggesting Smith normal form/elementary divisors. –  hardmath Jan 8 '13 at 19:54
    
Thanks. Smith normal form is, in a sense, a generalization of gcd and Bezout ($d_1$=gcd of entries, $d_1d_2$= gcd of 2x2 minors et cetera). –  Jyrki Lahtonen Jan 8 '13 at 19:57
    
Great answer. It indeed suggests that $C$ must have a special form in order to get what I want ... –  Wox Jan 9 '13 at 9:51
    
The question arose from this problem: consider $T_{c}+\mathbb{Z}^{n}$ where $T_{c}$ is a finite subset of $\mathbb{Q}^{n}$. Now consider a change of basis $C\in\text{GL}(n,\mathbb{Q})$. The lattice after a change of basis is $C^{-1}(T_{c}+\mathbb{Z}^{n})$. I was trying to see when $C^{-1}\cdot(T_{c}+\mathbb{Z}^{n})=T_{c}'+\mathbb{Z}^{n}$. Therefore I was trying to simplify $C^{-1}\cdot\mathbb{Z}^{n}$ first. –  Wox Jan 9 '13 at 9:57
    
Your SNF idea got me already further: if $C^{-1}=\frac{1}{m}U.D.V$ then $C^{-1}\cdot(T_{c}+\mathbb{Z}^{n})=T_{c}'+\mathbb{Z}^{n}$ can be written as $U.(\frac{1}{m}D.V.T_{c}+\frac{1}{m}D\mathbb{Z}^{n})=T_{c}'+\mathbb{Z}^{n}$ which only works when $\frac{1}{m}D.V.T_{c}+\frac{1}{m}D\mathbb{Z}^{n}=T_{c}''+\mathbb{Z}^{n}$. Therefore I need to find out when this holds (making my original question obsolete). –  Wox Jan 9 '13 at 14:12
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.