2
$\begingroup$

Given two full-rank $3\times3$ integer matrices $M_1$ and $M_2$, I am trying to find integer matrices $N_1$ and $N_2$ such that $M_1N_1$=$M_2N_2$, such that $\left|\det(M_1N_1)\right|$ is minimal.

edit: The $N_i$ are only required to within a similarity transformation (i.e., $\tilde{N}_i\sim U_iN_iV_i$, where $U_i$ and $V_i$ are unimodular integer matrices).

This seems analogous to finding the "least common multiple" of two integer matrices, but I'm having trouble identifying an algorithm or matrix decomposition that helps me.

I'm aware of the relationship of this problem to ring theory, in that the columns of the "LCM" matrix that I'm looking for generate the ideals formed by the intersection of the ideals generated by $M_1$ and $M_2$. I'm not very familiar with ring theory, but I tried rewriting the problem in terms of the Smith normal forms of $M_1$ and $M_2$, which didn't get me much closer to a solution.

Just for context, my ultimate goal is to find the (crystallographic) lattice formed by the coincident points of two other lattices (described by the lattice vectors $L_1=LM_1$ and $L_2=LM_2$).

$\endgroup$
5
  • $\begingroup$ if unimodular means "with determinant 1" then det$(M_1N_1)=$det$M_1$ always and... $\endgroup$
    – user126154
    Apr 27, 2015 at 14:56
  • $\begingroup$ if you drop the unimodular requirement, then the problem becames possible and the cofactor matrix help $\endgroup$
    – user126154
    Apr 27, 2015 at 14:58
  • $\begingroup$ Sorry if that was unclear-- $N_i$ is similar (for my purposes) to any $\tilde{N}_i=N_i U$, where $U$ is unimodular. $\det(M_1N_1)\ge lcm(\det(M_1)\det(M_2))$, and det(M_1) may be different from $\det(M_2)$ $\endgroup$
    – Fizzix
    Apr 27, 2015 at 15:02
  • $\begingroup$ ok. As I said, the matrix of cofactors does not solve a priori, but gives you a $N_1=\det M_2 Id$, which is optimal if det$M_1$ and det$M_2$ are coprime. For the general answer I don'tn know $\endgroup$
    – user126154
    Apr 27, 2015 at 15:23
  • $\begingroup$ do you require $N_i$ invertible? $\endgroup$
    – user126154
    Apr 27, 2015 at 15:33

2 Answers 2

1
$\begingroup$

This is only a partial answer. (I assume you want $N_1$ and $N_2$ invertible, otherwise $N_1=0$ solves)

Given $M$ its matrix of cofactors $\mathrm{Cof}(M)$ (see for instance here) is such that $\mathrm{Cof}(M)=M^{-1}\det M$. As $\mathrm{Cof}(M)$ is made by minors of $M$ if $M$ is integer then $\mathrm{Cof}(M)$ is.

If $M_2N_2=M_1N_1$ we have $$N_2=\frac{\mathrm{Cof}(M_2)M_1}{\det M_2}N_1$$

This is computable. Reduce so that $\frac{\mathrm{Cof}(M_2)M_1}{\det M_2}=A/n$ where $A$ is integer. Then we have $$\det N_2=\frac{\det A}{n^3}\det(N_1)$$ If $\frac{\det A}{n^3}$ is reduced, then you must have $\det N_1\geq n^3$ and $nId$ solves.

In general this reduces the problem to solve $$\frac{A}{n}N_1$$ integer with $|\det N_1|$ minimal.

$\endgroup$
3
  • 1
    $\begingroup$ $N_i$ don't have to be invertible on $\mathbb{Z}$ (which would require unimodularity), but they can't be indeterminate. Now that I think about it, the $M_i$ can also be right-multiplied by unimodular matrices $V_i$, so I can reduce your expression via $N_2=\frac{V^{-1}_2AV_1}{n} N_1$, which means I can choose $V_2$ and $V_1$ to form the Smith normal form of $A$ ($A=V_2 S V^{-1}_1$, with $S$ diagonal), From there I should be able to find an optimal solution in all cases. Sorry, I don't have enough reputation yet to vote your answer up. $\endgroup$
    – Fizzix
    Apr 27, 2015 at 16:10
  • 1
    $\begingroup$ Alright, I think I found the optimal solution: Taking the Smith normal form of $A=BST$, where $B$ and $T$ are unimodular and $S$ is diagonal (and $S(i,i)\mid S(i+1,i+1))$, an optimal solution can be constructed as $N_1=T^{-1}R$, where $R$ is diagonal with entries $R(i,i)=n/\mathrm{gcd}(S(i,i),n)$. Then $N_2=BSR$, and $\det(N_2)$ is minimized. I'm not sure what the protocol is for editing answers, so I'll leave this as a comment. $\endgroup$
    – Fizzix
    Apr 27, 2015 at 23:37
  • $\begingroup$ just click on "Post your answer" and use LaTeX for formulas, there is no particular protocol. you may want to read the help center math.stackexchange.com/help/answering $\endgroup$
    – user126154
    Apr 28, 2015 at 7:37
0
$\begingroup$

As mentioned in the last paragraph of the question, the least common multiple (LCM) of $3\times 3$ matrices $M_1$ and $M_2$ is a $3\times 3$ matrix $M'$ such that $$\mathcal L(M')=\mathcal L(M_1)\cap\mathcal L(M_2),$$ where $\mathcal L(M)=\{ M\mathbf k:\mathbf k\in\mathbb Z^d\}$ is the lattice generated by the $d$ columns of $M$. In lattice theory, if the columns of $M$ are linearly independent, we say they form a $\mathbb Z$-basis of $\mathcal L(M)$. In this question, finding $M'$ is equivalent to finding a basis of $\mathcal L(M_1)\cap\mathcal L(M_2)$, which has been solved in the question Basis for the intersection of two integer lattices. Accordingly, I shall briefly describe how to compute the LCM of two integer matrices $M_1,M_2$.

Given a lattice $\mathcal L$, we define its dual lattice as $$\mathcal L^\wedge=\{\mathbf v:\forall\mathbf w\in\mathcal L,\left<\mathbf v,\mathbf w\right>\in\mathbb Z\},$$ where $\left<\cdot,\cdot\right>$ stands for inner product. If $M$ is a basis of $\mathcal L(M)$, we have $$\begin{aligned} \mathcal L(M)^\wedge &=\{\mathbf v:\forall\mathbf k\in\mathbb Z^d,\left<\mathbf v,M\mathbf k\right>\in\mathbb Z\} \\&=\{\mathbf v:\forall\mathbf k\in\mathbb Z^d,\left<M^\text T\mathbf v,\mathbf k\right>\in\mathbb Z\} \\&=\{\mathbf v:M^\text T\mathbf v\in\mathbb Z^d\} \\&=\{(M^\text T)^{-1}\mathbf k:\mathbf k\in\mathbb Z^d\} .\end{aligned}$$ Hence, $(M^\text T)^{-1}$ is a basis of $\mathcal L(M)^\wedge$. We can see that $(\mathcal L^\wedge)^\wedge=\mathcal L$ since $(((M^\text T)^{-1})^\text T)^{-1}=M$.

Given two lattices $\mathcal L(M_1),\mathcal L(M_2)$, denote $$\mathcal L([M_1|M_2])=\{\mathbf v_1+\mathbf v_2:\mathbf v_1\in\mathcal L(M_1),\mathbf v_2\in\mathcal L(M_2)\},$$ which is generated by the columns of $M_1$ and $M_2$. Note that $$\begin{aligned} \mathcal L([M_1|M_2])^\wedge &=\{\mathbf v:\forall \mathbf w\in\mathcal L([M_1|M_2]),\left<\mathbf v,\mathbf w\right>\in\mathbb Z\} \\&=\{\mathbf v:\forall\mathbf w_1\in\mathcal L(M_1),\forall\mathbf w_2\in\mathcal L(M_2),\;\left<\mathbf v,\mathbf w_1+\mathbf w_2\right>\in\mathbb Z\} \\&=\{\mathbf v:\forall\mathbf w_1\in\mathcal L(M_1),\left<\mathbf v,\mathbf w_1\right>\in\mathbb Z,\;\forall\mathbf w_2\in\mathcal L(M_2),\left<\mathbf v,\mathbf w_2\right>\in\mathbb Z\} \\&=\mathcal L(M_1)^\wedge\cap\mathcal L(M_2)^\wedge .\end{aligned}$$ An immediate corollary is $$\begin{aligned} \mathcal L(M_1)\cap\mathcal L(M_2) &=(\mathcal L(M_1)^\wedge)^\wedge\cap(\mathcal L(M_2)^\wedge)^\wedge \\&=\mathcal L([(M_1^\text T)^{-1}|(M_2^\text T)^{-1}])^\wedge .\end{aligned}$$ The $3\times 6$ matrix $[(M_1^\text T)^{-1}|(M_2^\text T)^{-1}]$ can be turned into its Hermite normal form (HNF) via elementary column operations over $\mathbb Z$. In other words, we have $$[(M_1^\text T)^{-1}|(M_2^\text T)^{-1}]=[H|\mathbf 0_{3\times 3}]U,$$ where $U\in\operatorname{GL}(6,\mathbb Z)$, and $H$ is a $3\times 3$ matrix whose columns form a basis of $\mathcal L([(M_1^\text T)^{-1}|(M_2^\text T)^{-1}])$. Therefore we obtain $$\mathcal L(M_1)\cap\mathcal L(M_2)=\mathcal L((H^\text T)^{-1}).$$ So far, we see that $(H^\text T)^{-1}$ is a choice of $M_1N_1=M_2N_2$ such that $\left|\det(M_1N_1)\right|$ is minimal, since a basis of a lattice has the minimal nonzero absolute value of determinant, i.e., a primitive cell has the minimal nonzero volume.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .