Domain basis: Difference between revisions
Cmloegcmluin (talk | contribs) reorganize page to create an appropriate place to discuss interval basis intersections |
Cmloegcmluin (talk | contribs) |
||
| Line 410: | Line 410: | ||
= Intersecting = | = Intersecting = | ||
Finding the intersection of interval bases is surprisingly tricky<ref>This approach was found by Sintel here: https://math.stackexchange.com/questions/1560411/basis-for-the-intersection-of-two-integer-lattices/2472784#2472784</ref>: | |||
# Convert the interval bases to matrices, as with a merge. | |||
# Create a [[Wikipedia:Block_matrix|block matrix]] by stacking two copies of one interval basis on the left side, and then setting one copy of the other interval basis on the right side, with the bottom-right quadrant of this block matrix filled in with all zeros. | |||
# HNF this. | |||
# The results we want are in the bottom-right. We take only half-columns, from the bottom half, and only half-columns where their corresponding top-half are all zeros (which will only happen to columns that are sorted to the right side). | |||
# Canonicalize. | |||
== Example == | |||
Let's find the intersection of 2.5/3 and 2.9.5. | |||
First, the two interval bases as matrices: | |||
<math> | |||
\begin{array} {ccc} | |||
\begin{array} {ccc} \\ \end{array} \\ | |||
\begin{array} {rrr} | |||
\scriptsize{2} \\ | |||
\scriptsize{3} \\ | |||
\scriptsize{5} \\ | |||
\end{array} | |||
\end{array} | |||
\begin{array} {ccc} | |||
\begin{array} {ccc} | |||
\scriptsize{2} & \scriptsize{5/3} \\ | |||
\end{array} \\ | |||
\left[ \begin{array} {rrr} | |||
1 & 0 \\ | |||
0 & -1 \\ | |||
0 & 1 \\ | |||
\end{array} \right] | |||
\end{array} | |||
\hspace{1cm} | |||
\begin{array} {ccc} | |||
\begin{array} {ccc} \\ \end{array} \\ | |||
\begin{array} {rrr} | |||
\scriptsize{2} \\ | |||
\scriptsize{3} \\ | |||
\scriptsize{5} \\ | |||
\end{array} | |||
\end{array} | |||
\begin{array} {ccc} | |||
\begin{array} {ccc} | |||
\scriptsize{2} & \scriptsize{9} & \scriptsize{5} \\ | |||
\end{array} \\ | |||
\left[ \begin{array} {rrr} | |||
1 & 0 & 0 \\ | |||
0 & 2 & 0 \\ | |||
0 & 0 & 1 \\ | |||
\end{array} \right] | |||
\end{array} | |||
</math> | |||
Now we must combine them into one big block matrix. Two copies of the first on the left, one copy of the other in the top-right, and zeros to pad out: | |||
<math> | |||
\left[ \begin{array} {rr|rrr} | |||
1 & 0 & 1 & 0 & 0 \\ | |||
0 & -1 & 0 & 2 & 0 \\ | |||
0 & 1 & 0 & 0 & 1 \\ | |||
\hline | |||
1 & 0 & 0 & 0 & 0 \\ | |||
0 & -1 & 0 & 0 & 0 \\ | |||
0 & 1 & 0 & 0 & 0 \\ | |||
\end{array} \right] | |||
</math> | |||
Now, HNF that (column-style, so zeros end up in the top right): | |||
<math> | |||
\left[ \begin{array} {rrrrr} | |||
1 & 0 & 0 & 0 & 0 \\ | |||
0 & 1 & 0 & 0 & 0 \\ | |||
0 & 0 & 1 & 0 & 0 \\ | |||
0 & 0 & 0 & 1 & 0 \\ | |||
0 & 1 & 0 & 0 & 2 \\ | |||
0 & -1 & 0 & 0 & -2 \\ | |||
\end{array} \right] | |||
</math> | |||
Now we're looking for any half-columns in the bottom half wherever there are all zeroes in the corresponding top half. Such zeroes are highlighted red here, and what we're looking for is highlighted in yellow: | |||
<math> | |||
\left[ \begin{array} {rrrrr} | |||
1 & 0 & 0 & \colorbox{pink}0 & \colorbox{pink}0 \\ | |||
0 & 1 & 0 & \colorbox{pink}0 & \colorbox{pink}0 \\ | |||
0 & 0 & 1 & \colorbox{pink}0 & \colorbox{pink}0 \\ | |||
\hline | |||
0 & 0 & 0 & \colorbox{yellow}1 & \colorbox{yellow}0 \\ | |||
0 & 1 & 0 & \colorbox{yellow}0 & \colorbox{yellow}2 \\ | |||
0 & -1 & 0 & \colorbox{yellow}0 & \colorbox{yellow}{-2} \\ | |||
\end{array} \right] | |||
</math> | |||
So let's focus in on that result: | |||
<math> | |||
\left[ \begin{array} {rrr} | |||
1 & 0 \\ | |||
0 & 2 \\ | |||
0 & -2 \\ | |||
\end{array} \right] | |||
</math> | |||
Canonicalization time. That's already in matrix form, and HNF even (yes, we use HNF again here). No all zeros columns. Converted back to a list of numbers we at first have 2.9/25. But the last step is to take the undirected value, which reciprocates 9/25 to its super form which is 25/9. So the intersection of 2.5/3 and 2.9.5 is 2.25/9. | |||
= Changing interval basis = | = Changing interval basis = | ||