algebraeon_rings/module/
finitely_free_submodule.rs

1use super::{finitely_free_coset::*, finitely_free_module::*};
2use crate::{matrix::*, structure::*};
3use algebraeon_sets::structure::*;
4use std::{borrow::Borrow, fmt::Debug};
5
6#[derive(Debug, Clone)]
7pub struct FinitelyFreeSubmodule<Set: Clone + Debug> {
8    // a matrix in reduced hermite normal form with all non-zero rows whose rows form a basis for the submodule
9    row_basis: Matrix<Set>,
10    // the columns of the pivots of row_basis
11    pivots: Vec<usize>,
12}
13
14impl<Set: Clone + Debug> FinitelyFreeSubmodule<Set> {
15    pub fn into_row_basis_matrix(self) -> Matrix<Set> {
16        self.row_basis
17    }
18
19    pub fn into_col_basis_matrix(self) -> Matrix<Set> {
20        self.row_basis.transpose()
21    }
22
23    pub(crate) fn row_basis_matrix(&self) -> &Matrix<Set> {
24        &self.row_basis
25    }
26
27    pub fn basis(&self) -> Vec<Vec<Set>> {
28        (0..self.row_basis.rows())
29            .map(|r| {
30                (0..self.row_basis.cols())
31                    .map(|c| self.row_basis.at(r, c).unwrap().clone())
32                    .collect()
33            })
34            .collect()
35    }
36
37    pub fn rank(&self) -> usize {
38        self.row_basis.rows()
39    }
40
41    pub fn module_rank(&self) -> usize {
42        self.row_basis.cols()
43    }
44}
45
46#[derive(Debug, Clone, PartialEq, Eq)]
47pub struct FinitelyFreeSubmoduleStructure<
48    Ring: ReducedHermiteAlgorithmSignature,
49    RingB: BorrowedStructure<Ring>,
50> {
51    module: FinitelyFreeModuleStructure<Ring, RingB>,
52}
53
54impl<Ring: ReducedHermiteAlgorithmSignature, RingB: BorrowedStructure<Ring>>
55    FinitelyFreeSubmoduleStructure<Ring, RingB>
56{
57    pub fn new(module: FinitelyFreeModuleStructure<Ring, RingB>) -> Self {
58        Self { module }
59    }
60}
61
62impl<Ring: ReducedHermiteAlgorithmSignature, RingB: BorrowedStructure<Ring>> Signature
63    for FinitelyFreeSubmoduleStructure<Ring, RingB>
64{
65}
66
67impl<Ring: ReducedHermiteAlgorithmSignature, RingB: BorrowedStructure<Ring>> SetSignature
68    for FinitelyFreeSubmoduleStructure<Ring, RingB>
69{
70    type Set = FinitelyFreeSubmodule<Ring::Set>;
71
72    fn is_element(&self, x: &Self::Set) -> Result<(), String> {
73        if x.row_basis.cols() != self.module.rank() {
74            return Err("dimensions don't match".to_string());
75        }
76        // TODO: more checks
77        Ok(())
78    }
79}
80
81impl<Ring: ReducedHermiteAlgorithmSignature, RingB: BorrowedStructure<Ring>>
82    FinitelyFreeSubmoduleStructure<Ring, RingB>
83{
84    pub fn module(&self) -> &FinitelyFreeModuleStructure<Ring, RingB> {
85        &self.module
86    }
87
88    pub fn ring(&self) -> &Ring {
89        self.module().ring()
90    }
91
92    pub fn matrix_row_span_and_basis(
93        &self,
94        matrix: Matrix<Ring::Set>,
95    ) -> (FinitelyFreeSubmodule<Ring::Set>, Matrix<Ring::Set>) {
96        let ring = self.ring();
97        let rows = matrix.rows();
98        let cols = matrix.cols();
99        debug_assert_eq!(cols, self.module().rank());
100        let (h, u, _det, pivots) =
101            MatrixStructure::new(ring.clone()).row_reduced_hermite_algorithm(matrix);
102        let row_basis = h.submatrix((0..pivots.len()).collect(), (0..cols).collect());
103        let u = u.submatrix((0..pivots.len()).collect(), (0..rows).collect());
104        (FinitelyFreeSubmodule { row_basis, pivots }, u)
105    }
106
107    pub fn matrix_col_span_and_basis(
108        &self,
109        matrix: Matrix<Ring::Set>,
110    ) -> (FinitelyFreeSubmodule<Ring::Set>, Matrix<Ring::Set>) {
111        let (s, u) = self.matrix_row_span_and_basis(matrix.transpose());
112        (s, u.transpose())
113    }
114
115    pub fn matrix_row_span(&self, matrix: Matrix<Ring::Set>) -> FinitelyFreeSubmodule<Ring::Set> {
116        self.matrix_row_span_and_basis(matrix).0
117    }
118
119    pub fn matrix_col_span(&self, matrix: Matrix<Ring::Set>) -> FinitelyFreeSubmodule<Ring::Set> {
120        self.matrix_col_span_and_basis(matrix).0
121    }
122
123    pub fn span(&self, span: Vec<impl Borrow<Vec<Ring::Set>>>) -> FinitelyFreeSubmodule<Ring::Set> {
124        for v in &span {
125            debug_assert_eq!(v.borrow().len(), self.module().rank());
126        }
127        self.matrix_row_span(Matrix::construct(
128            span.len(),
129            self.module().rank(),
130            |r, c| span[r].borrow()[c].clone(),
131        ))
132    }
133
134    pub fn kernel(
135        &self,
136        items: Vec<impl Borrow<Vec<Ring::Set>>>,
137    ) -> FinitelyFreeSubmodule<Ring::Set> {
138        let n = self.module().rank();
139        debug_assert_eq!(items.len(), n);
140        if n == 0 {
141            self.zero_submodule()
142        } else {
143            let cols = items.first().unwrap().borrow().len();
144            for v in &items[1..] {
145                assert_eq!(v.borrow().len(), cols);
146            }
147            self.matrix_row_kernel(Matrix::construct(n, cols, |r, c| {
148                items[r].borrow()[c].clone()
149            }))
150        }
151    }
152
153    pub fn matrix_row_preimage(
154        &self,
155        matrix: &Matrix<Ring::Set>,
156        space: &FinitelyFreeSubmodule<Ring::Set>,
157    ) -> FinitelyFreeSubmodule<Ring::Set> {
158        debug_assert_eq!(matrix.rows(), self.module().rank());
159        debug_assert_eq!(matrix.cols(), space.module_rank());
160        /*
161        Let M be the matrix and S a row basis matrix for the space.
162        Need to solve xM=yS for all possible x
163        So concat the rows of M over the rows of S to get a matrix A
164        Solve for the kernel of A and take only the first bits corresponding to x
165        */
166        let a = Matrix::join_rows(matrix.cols(), vec![&matrix, space.row_basis_matrix()]);
167        // Find a row U such that uA is in HNF
168        // The kernel of UA is standard basis vectors pivs.len()..a.rows()
169        // So the kernel of A is the rows pivs.len()..a.rows() of U
170        // And we are after the span of the first matrix.rows() of them
171        let (h, u, _u_det, pivs) =
172            MatrixStructure::<Ring, _>::new(self.ring()).row_hermite_algorithm(a);
173
174        self.matrix_row_span(u.submatrix(
175            (pivs.len()..h.rows()).collect(),
176            (0..matrix.rows()).collect(),
177        ))
178    }
179
180    pub fn matrix_col_preimage(
181        &self,
182        matrix: &Matrix<Ring::Set>,
183        space: &FinitelyFreeSubmodule<Ring::Set>,
184    ) -> FinitelyFreeSubmodule<Ring::Set> {
185        self.matrix_row_preimage(&matrix.transpose_ref(), space)
186    }
187
188    pub fn matrix_row_kernel(&self, matrix: Matrix<Ring::Set>) -> FinitelyFreeSubmodule<Ring::Set> {
189        debug_assert_eq!(matrix.rows(), self.module().rank());
190        let rows = matrix.rows();
191        let (_h, u, _u_det, pivs) =
192            MatrixStructure::<Ring, _>::new(self.ring()).row_hermite_algorithm(matrix);
193        debug_assert_eq!(rows, u.rows());
194        debug_assert_eq!(rows, u.cols());
195        let ker = u.submatrix((pivs.len()..rows).collect(), (0..rows).collect());
196        self.matrix_row_span(ker)
197    }
198
199    pub fn matrix_col_kernel(&self, matrix: Matrix<Ring::Set>) -> FinitelyFreeSubmodule<Ring::Set> {
200        debug_assert_eq!(matrix.cols(), self.module().rank());
201        self.matrix_row_kernel(matrix.transpose())
202    }
203
204    pub fn full_submodule(&self) -> FinitelyFreeSubmodule<Ring::Set> {
205        self.matrix_row_span(
206            MatrixStructure::<Ring, _>::new(self.ring().clone()).ident(self.module().rank()),
207        )
208    }
209
210    pub fn zero_submodule(&self) -> FinitelyFreeSubmodule<Ring::Set> {
211        let cols = self.module().rank();
212        FinitelyFreeSubmodule {
213            row_basis: Matrix::construct(0, cols, |_, _| unreachable!()),
214            pivots: vec![],
215        }
216    }
217
218    pub fn reduce_element(
219        &self,
220        submodule: &FinitelyFreeSubmodule<Ring::Set>,
221        element: &Vec<Ring::Set>,
222    ) -> (Vec<Ring::Set>, Vec<Ring::Set>) {
223        debug_assert!(self.is_element(submodule).is_ok());
224        debug_assert!(self.module().is_element(element).is_ok());
225        let mut reduced_element = element.clone();
226        let mut coset = vec![];
227        for (r, &c) in submodule.pivots.iter().enumerate() {
228            let quo = self
229                .ring()
230                .quo(&reduced_element[c], submodule.row_basis.at(r, c).unwrap())
231                .unwrap();
232            #[allow(clippy::needless_range_loop)]
233            for c2 in 0..self.module().rank() {
234                reduced_element[c2] = self.ring().add(
235                    &reduced_element[c2],
236                    &self.ring().neg(
237                        &self
238                            .ring()
239                            .mul(&quo, submodule.row_basis.at(r, c2).unwrap()),
240                    ),
241                );
242            }
243            coset.push(quo);
244        }
245        (coset, reduced_element)
246    }
247
248    pub fn equal_slow(
249        &self,
250        x: &FinitelyFreeSubmodule<Ring::Set>,
251        y: &FinitelyFreeSubmodule<Ring::Set>,
252    ) -> bool {
253        debug_assert!(self.is_element(x).is_ok());
254        debug_assert!(self.is_element(y).is_ok());
255        self.contains(x, y) && self.contains(y, x)
256    }
257
258    pub fn contains_element(
259        &self,
260        submodule: &FinitelyFreeSubmodule<Ring::Set>,
261        element: &Vec<Ring::Set>,
262    ) -> bool {
263        debug_assert!(self.is_element(submodule).is_ok());
264        debug_assert!(self.module().is_element(element).is_ok());
265        let (_offset, element_reduced) = self.reduce_element(submodule, element);
266        element_reduced
267            .iter()
268            .all(|coeff| self.ring().is_zero(coeff))
269    }
270
271    pub fn contains(
272        &self,
273        x: &FinitelyFreeSubmodule<Ring::Set>,
274        y: &FinitelyFreeSubmodule<Ring::Set>,
275    ) -> bool {
276        debug_assert!(self.is_element(x).is_ok());
277        debug_assert!(self.is_element(y).is_ok());
278        for b in y.basis() {
279            if !self.contains_element(x, &b) {
280                return false;
281            }
282        }
283        true
284    }
285
286    pub fn add(
287        &self,
288        x: FinitelyFreeSubmodule<Ring::Set>,
289        y: FinitelyFreeSubmodule<Ring::Set>,
290    ) -> FinitelyFreeSubmodule<Ring::Set> {
291        self.sum(vec![x, y])
292    }
293
294    pub fn sum(
295        &self,
296        xs: Vec<FinitelyFreeSubmodule<Ring::Set>>,
297    ) -> FinitelyFreeSubmodule<Ring::Set> {
298        for x in &xs {
299            debug_assert!(self.is_element(x).is_ok());
300        }
301        let cols = self.module().rank();
302        self.matrix_row_span(Matrix::join_rows(
303            cols,
304            xs.into_iter().map(|x| x.into_row_basis_matrix()).collect(),
305        ))
306    }
307
308    pub fn intersect(
309        &self,
310        x: FinitelyFreeSubmodule<Ring::Set>,
311        y: FinitelyFreeSubmodule<Ring::Set>,
312    ) -> FinitelyFreeSubmodule<Ring::Set> {
313        debug_assert!(self.is_element(&x).is_ok());
314        debug_assert!(self.is_element(&y).is_ok());
315
316        let cols = self.module().rank();
317        let x_rows = x.into_row_basis_matrix();
318        let y_rows = y.into_row_basis_matrix();
319        let matrix = Matrix::join_rows(cols, vec![&x_rows, &y_rows]);
320        let matrix_ker = self
321            .ring()
322            .free_module(matrix.rows())
323            .submodules()
324            .matrix_row_kernel(matrix)
325            .into_row_basis_matrix();
326        let matrix_ker_first_part = matrix_ker.submatrix(
327            (0..matrix_ker.rows()).collect(),
328            (0..x_rows.rows()).collect(),
329        );
330        self.matrix_row_span(
331            MatrixStructure::<Ring, _>::new(self.ring())
332                .mul(&matrix_ker_first_part, &x_rows)
333                .unwrap(),
334        )
335    }
336
337    pub fn intersect_list(
338        &self,
339        mut xs: Vec<FinitelyFreeSubmodule<Ring::Set>>,
340    ) -> FinitelyFreeSubmodule<Ring::Set> {
341        if let Some(a) = xs.pop() {
342            if let Some(b) = xs.pop() {
343                let mut i = self.intersect(a, b);
344                for c in xs {
345                    i = self.intersect(i, c);
346                }
347                i
348            } else {
349                a
350            }
351        } else {
352            self.full_submodule()
353        }
354    }
355
356    //given x contained in y, find rank(y) - rank(x) basis vectors needed to extend x to y
357    pub fn extension_basis(
358        &self,
359        x: &FinitelyFreeSubmodule<Ring::Set>,
360        y: &FinitelyFreeSubmodule<Ring::Set>,
361    ) -> Vec<Vec<Ring::Set>> {
362        debug_assert!(self.is_element(x).is_ok());
363        debug_assert!(self.is_element(y).is_ok());
364
365        //https://math.stackexchange.com/questions/2554408/how-to-find-the-basis-of-a-quotient-space
366        debug_assert!(self.contains(y, x));
367
368        let n = self.module().rank();
369        // form matrix of all vectors from [other self]
370        // row reduce and get pivots - take cols from orig to form basies of the quotient space
371
372        let mat_structure = MatrixStructure::<Ring, _>::new(self.ring());
373        let row_span = Matrix::join_rows(n, vec![&x.row_basis, &y.row_basis]);
374        let (_h, _u, _u_det, pivs) = mat_structure.col_hermite_algorithm(row_span.clone());
375
376        let mut extension_basis = vec![];
377        for r in pivs {
378            //dont take vectors which form a basis of lat_a
379            if r >= x.rank() {
380                extension_basis.push(row_span.get_row(r));
381            }
382        }
383
384        debug_assert_eq!(x.rank() + extension_basis.len(), y.rank());
385
386        extension_basis
387    }
388
389    pub fn coset(
390        &self,
391        x: &FinitelyFreeSubmodule<Ring::Set>,
392        offset: &Vec<Ring::Set>,
393    ) -> FinitelyFreeSubmoduleCoset<Ring::Set> {
394        self.module()
395            .cosets()
396            .from_offset_and_submodule(offset, x.clone())
397    }
398
399    pub fn into_coset(
400        &self,
401        x: FinitelyFreeSubmodule<Ring::Set>,
402    ) -> FinitelyFreeSubmoduleCoset<Ring::Set> {
403        self.module()
404            .cosets()
405            .from_offset_and_submodule(&self.module().zero(), x)
406    }
407}
408
409impl<Ring: UniqueReducedHermiteAlgorithmSignature, RingB: BorrowedStructure<Ring>> EqSignature
410    for FinitelyFreeSubmoduleStructure<Ring, RingB>
411{
412    fn equal(
413        &self,
414        x: &FinitelyFreeSubmodule<Ring::Set>,
415        y: &FinitelyFreeSubmodule<Ring::Set>,
416    ) -> bool {
417        debug_assert!(self.is_element(x).is_ok());
418        debug_assert!(self.is_element(y).is_ok());
419        MatrixStructure::<Ring, _>::new(self.ring()).equal(&x.row_basis, &y.row_basis)
420    }
421}
422
423#[cfg(test)]
424mod tests {
425    use super::*;
426    use algebraeon_nzq::{Integer, Rational};
427
428    #[test]
429    fn test_finitely_free_submodule_kernel() {
430        let submodules = Integer::structure().into_free_module(3).into_submodules();
431
432        let a = submodules.span(vec![&vec![1.into(), 1.into(), (-1).into()]]);
433
434        let b = submodules.kernel(vec![
435            &vec![1.into(), 1.into(), 2.into(), 2.into()],
436            &vec![2.into(), 2.into(), 1.into(), 1.into()],
437            &vec![3.into(), 3.into(), 3.into(), 3.into()],
438        ]);
439
440        assert!(submodules.equal(&a, &b));
441    }
442
443    #[test]
444    fn test_finitely_free_submodule_reduction() {
445        let a = Matrix::from_rows(vec![vec![1, 2, 4, 5], vec![1, 2, 3, 4]]);
446        a.pprint();
447        let a_reduced = Integer::structure()
448            .free_module(4)
449            .submodules()
450            .matrix_row_span(a)
451            .into_row_basis_matrix();
452        let a_expected = Matrix::from_rows(vec![vec![1, 2, 0, 1], vec![0, 0, 1, 1]]);
453        a_reduced.pprint();
454        a_expected.pprint();
455        assert_eq!(a_reduced, a_expected);
456    }
457
458    #[test]
459    fn test_finitely_free_submodule_unreduced_equal() {
460        let modules = Integer::structure().into_free_module(4);
461        assert!(
462            modules.submodules().equal(
463                &modules
464                    .submodules()
465                    .matrix_row_span(Matrix::from_rows(vec![vec![1, 2, 3, 4], vec![0, 0, 1, 1]])),
466                &modules
467                    .submodules()
468                    .matrix_row_span(Matrix::from_rows(vec![vec![1, 2, 0, 1], vec![0, 0, 1, 1]]))
469            )
470        );
471    }
472
473    #[test]
474    fn test_finitely_free_submodule_intersect() {
475        let modules = Integer::structure().into_free_module(4);
476
477        let a = modules.submodules().matrix_row_span(Matrix::from_rows(vec![
478            vec![2, 0, 0, 0],
479            vec![0, 2, 0, 0],
480            vec![0, 0, 2, 0],
481            vec![0, 0, 0, 2],
482        ]));
483
484        let b = modules.submodules().matrix_row_span(Matrix::from_rows(vec![
485            vec![3, 3, 3, 3],
486            vec![3, 3, -3, -3],
487        ]));
488
489        let c = modules
490            .submodules()
491            .matrix_row_span(Matrix::from_rows(vec![vec![6, 6, 0, 0], vec![0, 0, 6, 6]]));
492
493        let s = modules.submodules().intersect(a, b);
494
495        s.clone().into_row_basis_matrix().pprint();
496
497        assert!(modules.submodules().equal(&c, &s));
498    }
499
500    #[test]
501    fn test_finitely_free_submodule_element_reduction() {
502        let modules = Integer::structure().into_free_module(4);
503
504        let a = modules.submodules().matrix_row_span(Matrix::from_rows(vec![
505            vec![3, 2, 0, 3],
506            vec![0, 14, 3, 1],
507            vec![0, 0, 0, 10],
508        ]));
509        a.clone().into_row_basis_matrix().pprint();
510
511        let element = vec![20, 20, 20, 20]
512            .into_iter()
513            .map(Integer::from)
514            .collect::<Vec<_>>();
515        println!("element = {:?}", element);
516
517        let (offset, reduced_element) = modules.submodules().reduce_element(&a, &element);
518
519        println!("offset = {:?}", offset);
520        println!("reduced_element = {:?}", reduced_element);
521        debug_assert_eq!(
522            reduced_element,
523            vec![2, 8, 20, 2]
524                .into_iter()
525                .map(Integer::from)
526                .collect::<Vec<_>>()
527        );
528    }
529
530    #[test]
531    fn test_finitely_free_submodule_extension_basis() {
532        let modules = Rational::structure().into_free_module(3);
533
534        let a = Matrix::<Rational>::from_rows(vec![vec![1, 0, 0], vec![1, 0, 0], vec![-1, 0, 0]]);
535
536        let b = Matrix::<Rational>::from_rows(vec![vec![1, 1, 0], vec![1, 1, 0], vec![1, -1, 0]]);
537
538        println!("a");
539        a.pprint();
540        println!("b");
541        b.pprint();
542
543        let ext = modules
544            .submodules()
545            .extension_basis(&a.col_span(), &b.col_span());
546
547        println!("ext");
548        for v in ext {
549            println!("{:?}", v);
550        }
551    }
552}
algebraeon_rings/module/finitely_free_submodule.rs

algebraeon_rings/module/
finitely_free_submodule.rs
