algebraeon_rings/module/
finitely_free_module.rs

1use super::{
2    finitely_free_affine::FinitelyFreeSubmoduleAffineSubsetStructure,
3    finitely_free_coset::FinitelyFreeSubmoduleCosetStructure,
4    finitely_free_submodule::{FinitelyFreeSubmodule, FinitelyFreeSubmoduleStructure},
5};
6use crate::{
7    matrix::{Matrix, MatrixStructure, ReducedHermiteAlgorithmSignature},
8    structure::*,
9};
10use algebraeon_sets::structure::*;
11use std::{borrow::Cow, marker::PhantomData};
12
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct FinitelyFreeModuleStructure<Ring: RingSignature, RingB: BorrowedStructure<Ring>> {
15    _ring: PhantomData<Ring>,
16    ring: RingB,
17    basis_set: EnumeratedFiniteSetStructure,
18}
19
20impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> FinitelyFreeModuleStructure<Ring, RingB> {
21    pub fn new(ring: RingB, rank: usize) -> Self {
22        Self {
23            _ring: PhantomData,
24            ring,
25            basis_set: EnumeratedFiniteSetStructure::new(rank),
26        }
27    }
28}
29pub trait RingToFinitelyFreeModuleSignature: RingSignature {
30    fn free_module(&self, n: usize) -> FinitelyFreeModuleStructure<Self, &Self> {
31        FinitelyFreeModuleStructure::new(self, n)
32    }
33
34    fn into_free_module(self, n: usize) -> FinitelyFreeModuleStructure<Self, Self> {
35        FinitelyFreeModuleStructure::new(self, n)
36    }
37}
38impl<Ring: RingSignature> RingToFinitelyFreeModuleSignature for Ring {}
39
40impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> FinitelyFreeModuleStructure<Ring, RingB> {
41    pub fn ring(&self) -> &Ring {
42        self.ring.borrow()
43    }
44
45    pub fn to_col(&self, v: &<Self as SetSignature>::Set) -> Matrix<Ring::Set> {
46        debug_assert!(self.is_element(v).is_ok());
47        Matrix::construct(self.rank(), 1, |r, _| v[r].clone())
48    }
49
50    pub fn to_row(&self, v: &<Self as SetSignature>::Set) -> Matrix<Ring::Set> {
51        debug_assert!(self.is_element(v).is_ok());
52        Matrix::construct(1, self.rank(), |_, c| v[c].clone())
53    }
54
55    pub fn from_row(&self, m: &Matrix<Ring::Set>) -> <Self as SetSignature>::Set {
56        debug_assert_eq!(m.rows(), 1);
57        debug_assert_eq!(m.cols(), self.rank());
58        (0..self.rank())
59            .map(|i| m.at(0, i).unwrap().clone())
60            .collect()
61    }
62
63    pub fn from_col(&self, m: &Matrix<Ring::Set>) -> <Self as SetSignature>::Set {
64        debug_assert_eq!(m.cols(), 1);
65        debug_assert_eq!(m.rows(), self.rank());
66        (0..self.rank())
67            .map(|i| m.at(i, 0).unwrap().clone())
68            .collect()
69    }
70
71    pub fn basis_element(&self, i: usize) -> <Self as SetSignature>::Set {
72        debug_assert!(i < self.rank());
73        (0..self.rank())
74            .map(|j| {
75                if i == j {
76                    self.ring().one()
77                } else {
78                    self.ring().zero()
79                }
80            })
81            .collect()
82    }
83}
84
85impl<Ring: ReducedHermiteAlgorithmSignature, RingB: BorrowedStructure<Ring>>
86    FinitelyFreeModuleStructure<Ring, RingB>
87{
88    pub fn submodules(&self) -> FinitelyFreeSubmoduleStructure<Ring, &Ring> {
89        FinitelyFreeSubmoduleStructure::new(FinitelyFreeModuleStructure::new(
90            self.ring(),
91            self.rank(),
92        ))
93    }
94
95    pub fn into_submodules(self) -> FinitelyFreeSubmoduleStructure<Ring, RingB> {
96        FinitelyFreeSubmoduleStructure::new(self)
97    }
98
99    pub fn cosets(&self) -> FinitelyFreeSubmoduleCosetStructure<Ring, &Ring> {
100        FinitelyFreeSubmoduleCosetStructure::new(FinitelyFreeModuleStructure::new(
101            self.ring(),
102            self.rank(),
103        ))
104    }
105
106    pub fn into_cosets(self) -> FinitelyFreeSubmoduleCosetStructure<Ring, RingB> {
107        FinitelyFreeSubmoduleCosetStructure::new(self)
108    }
109
110    pub fn affine_subsets(&self) -> FinitelyFreeSubmoduleAffineSubsetStructure<Ring, &Ring> {
111        FinitelyFreeSubmoduleAffineSubsetStructure::new(FinitelyFreeModuleStructure::new(
112            self.ring(),
113            self.rank(),
114        ))
115    }
116
117    pub fn into_affine_subsets(self) -> FinitelyFreeSubmoduleAffineSubsetStructure<Ring, RingB> {
118        FinitelyFreeSubmoduleAffineSubsetStructure::new(self)
119    }
120
121    pub fn improper_submodule(&self) -> FinitelyFreeSubmodule<Ring::Set> {
122        self.submodules()
123            .matrix_row_span(MatrixStructure::new(self.ring().clone()).ident(self.rank()))
124    }
125
126    pub fn generated_submodule(
127        &self,
128        generators: Vec<&Vec<Ring::Set>>,
129    ) -> FinitelyFreeSubmodule<Ring::Set> {
130        for generator in &generators {
131            debug_assert!(self.is_element(generator).is_ok());
132        }
133        let row_span = Matrix::construct(generators.len(), self.rank(), |r, c| {
134            generators[r][c].clone()
135        });
136        self.submodules().matrix_row_span(row_span)
137    }
138}
139
140impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> Signature
141    for FinitelyFreeModuleStructure<Ring, RingB>
142{
143}
144
145impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> SetSignature
146    for FinitelyFreeModuleStructure<Ring, RingB>
147{
148    type Set = Vec<Ring::Set>;
149
150    fn is_element(&self, v: &Self::Set) -> Result<(), String> {
151        if self.rank() != v.len() {
152            return Err("wrong size".to_string());
153        }
154        for r in v {
155            self.ring().is_element(r)?;
156        }
157        Ok(())
158    }
159}
160
161impl<Ring: RingSignature + EqSignature, RingB: BorrowedStructure<Ring>> EqSignature
162    for FinitelyFreeModuleStructure<Ring, RingB>
163{
164    fn equal(&self, v: &Self::Set, w: &Self::Set) -> bool {
165        debug_assert!(self.is_element(v).is_ok());
166        debug_assert!(self.is_element(w).is_ok());
167        (0..self.rank()).all(|i| self.ring().equal(&v[i], &w[i]))
168    }
169}
170
171impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> RinglikeSpecializationSignature
172    for FinitelyFreeModuleStructure<Ring, RingB>
173{
174}
175
176impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> ZeroSignature
177    for FinitelyFreeModuleStructure<Ring, RingB>
178{
179    fn zero(&self) -> Self::Set {
180        (0..self.rank()).map(|_| self.ring().zero()).collect()
181    }
182}
183
184impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> AdditionSignature
185    for FinitelyFreeModuleStructure<Ring, RingB>
186{
187    fn add(&self, v: &Self::Set, w: &Self::Set) -> Self::Set {
188        debug_assert!(self.is_element(v).is_ok());
189        debug_assert!(self.is_element(w).is_ok());
190        (0..self.rank())
191            .map(|i| self.ring().add(&v[i], &w[i]))
192            .collect()
193    }
194}
195
196impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> CancellativeAdditionSignature
197    for FinitelyFreeModuleStructure<Ring, RingB>
198{
199    fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
200        Some(self.sub(a, b))
201    }
202}
203
204impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> TryNegateSignature
205    for FinitelyFreeModuleStructure<Ring, RingB>
206{
207    fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
208        Some(self.neg(a))
209    }
210}
211
212impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> AdditiveMonoidSignature
213    for FinitelyFreeModuleStructure<Ring, RingB>
214{
215}
216
217impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> AdditiveGroupSignature
218    for FinitelyFreeModuleStructure<Ring, RingB>
219{
220    fn neg(&self, v: &Self::Set) -> Self::Set {
221        debug_assert!(self.is_element(v).is_ok());
222        v.iter().map(|r| self.ring().neg(r)).collect()
223    }
224
225    fn sub(&self, v: &Self::Set, w: &Self::Set) -> Self::Set {
226        debug_assert!(self.is_element(v).is_ok());
227        debug_assert!(self.is_element(w).is_ok());
228        (0..self.rank())
229            .map(|i| self.ring().sub(&v[i], &w[i]))
230            .collect()
231    }
232}
233
234impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> SemiModuleSignature<Ring>
235    for FinitelyFreeModuleStructure<Ring, RingB>
236{
237    fn ring(&self) -> &Ring {
238        self.ring.borrow()
239    }
240
241    fn scalar_mul(&self, v: &Self::Set, r: &Ring::Set) -> Self::Set {
242        debug_assert!(self.is_element(v).is_ok());
243        v.iter().map(|s| self.ring().mul(r, s)).collect()
244    }
245}
246
247impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> FreeModuleSignature<Ring>
248    for FinitelyFreeModuleStructure<Ring, RingB>
249{
250    type Basis = EnumeratedFiniteSetStructure;
251
252    fn basis_set(&self) -> impl std::borrow::Borrow<Self::Basis> {
253        &self.basis_set
254    }
255
256    fn to_component<'a>(&self, b: &usize, v: &'a Self::Set) -> Cow<'a, Ring::Set> {
257        debug_assert!(*b < self.rank());
258        Cow::Borrowed(&v[*b])
259    }
260
261    fn from_component(&self, b: &usize, r: &<Ring>::Set) -> Self::Set {
262        debug_assert!(*b < self.rank());
263        let mut element = self.zero();
264        element[*b] = r.clone();
265        element
266    }
267}
268
269// linear maps of finite rank free modules with a basis
270#[derive(Debug, Clone)]
271pub struct FreeModuleFiniteNumberedBasisLinearTransformation<
272    Ring: RingSignature,
273    RingB: BorrowedStructure<Ring>,
274    RingDomainB: BorrowedStructure<Ring>,
275    RingRangeB: BorrowedStructure<Ring>,
276    const INJECTIVE: bool,
277    const SURJECTIVE: bool,
278> {
279    ring: RingB,
280    domain: FinitelyFreeModuleStructure<Ring, RingDomainB>,
281    range: FinitelyFreeModuleStructure<Ring, RingRangeB>,
282    matrix: Matrix<Ring::Set>, // v -> Mv
283}
284
285impl<
286    Ring: BezoutDomainSignature,
287    RingB: BorrowedStructure<Ring>,
288    RingDomainB: BorrowedStructure<Ring>,
289    RingRangeB: BorrowedStructure<Ring>,
290    const INJECTIVE: bool,
291    const SURJECTIVE: bool,
292>
293    FreeModuleFiniteNumberedBasisLinearTransformation<
294        Ring,
295        RingB,
296        RingDomainB,
297        RingRangeB,
298        INJECTIVE,
299        SURJECTIVE,
300    >
301{
302    pub fn new(
303        ring: RingB,
304        domain: FinitelyFreeModuleStructure<Ring, RingDomainB>,
305        range: FinitelyFreeModuleStructure<Ring, RingRangeB>,
306        matrix: Matrix<Ring::Set>,
307    ) -> Self {
308        debug_assert_eq!(ring.borrow(), domain.ring());
309        debug_assert_eq!(ring.borrow(), range.ring());
310        debug_assert_eq!(domain.rank(), matrix.cols());
311        debug_assert_eq!(range.rank(), matrix.rows());
312        let rank = MatrixStructure::<Ring, _>::new(ring.borrow()).rank(matrix.clone());
313        if INJECTIVE {
314            debug_assert_eq!(rank, domain.rank());
315        }
316        if SURJECTIVE {
317            debug_assert_eq!(rank, range.rank());
318        }
319        Self {
320            ring,
321            domain,
322            range,
323            matrix,
324        }
325    }
326
327    fn construct_impl(
328        ring: RingB,
329        domain: FinitelyFreeModuleStructure<Ring, RingDomainB>,
330        range: FinitelyFreeModuleStructure<Ring, RingRangeB>,
331        basis_image: impl Fn(usize) -> Vec<Ring::Set>,
332    ) -> Self {
333        let matrix = Matrix::from_cols(
334            (0..domain.rank())
335                .map(|i| {
336                    let img_i = basis_image(i);
337                    debug_assert!(range.is_element(&img_i).is_ok());
338                    img_i
339                })
340                .collect(),
341        );
342        Self::new(ring, domain, range, matrix)
343    }
344}
345
346impl<
347    Ring: BezoutDomainSignature,
348    RingB: BorrowedStructure<Ring>,
349    RingDomainB: BorrowedStructure<Ring>,
350    RingRangeB: BorrowedStructure<Ring>,
351>
352    FreeModuleFiniteNumberedBasisLinearTransformation<
353        Ring,
354        RingB,
355        RingDomainB,
356        RingRangeB,
357        false,
358        false,
359    >
360{
361    pub fn construct(
362        ring: RingB,
363        domain: FinitelyFreeModuleStructure<Ring, RingDomainB>,
364        range: FinitelyFreeModuleStructure<Ring, RingRangeB>,
365        basis_image: impl Fn(usize) -> Vec<Ring::Set>,
366    ) -> Self {
367        Self::construct_impl(ring, domain, range, basis_image)
368    }
369}
370
371impl<
372    Ring: BezoutDomainSignature,
373    RingB: BorrowedStructure<Ring>,
374    RingDomainB: BorrowedStructure<Ring>,
375    RingRangeB: BorrowedStructure<Ring>,
376>
377    FreeModuleFiniteNumberedBasisLinearTransformation<
378        Ring,
379        RingB,
380        RingDomainB,
381        RingRangeB,
382        true,
383        false,
384    >
385{
386    pub fn construct_injective(
387        ring: RingB,
388        domain: FinitelyFreeModuleStructure<Ring, RingDomainB>,
389        range: FinitelyFreeModuleStructure<Ring, RingRangeB>,
390        basis_image: impl Fn(usize) -> Vec<Ring::Set>,
391    ) -> Self {
392        Self::construct_impl(ring, domain, range, basis_image)
393    }
394}
395
396impl<
397    Ring: BezoutDomainSignature,
398    RingB: BorrowedStructure<Ring>,
399    RingDomainB: BorrowedStructure<Ring>,
400    RingRangeB: BorrowedStructure<Ring>,
401>
402    FreeModuleFiniteNumberedBasisLinearTransformation<
403        Ring,
404        RingB,
405        RingDomainB,
406        RingRangeB,
407        false,
408        true,
409    >
410{
411    pub fn construct_surjective(
412        ring: RingB,
413        domain: FinitelyFreeModuleStructure<Ring, RingDomainB>,
414        range: FinitelyFreeModuleStructure<Ring, RingRangeB>,
415        basis_image: impl Fn(usize) -> Vec<Ring::Set>,
416    ) -> Self {
417        Self::construct_impl(ring, domain, range, basis_image)
418    }
419}
420
421impl<
422    Ring: BezoutDomainSignature,
423    RingB: BorrowedStructure<Ring>,
424    RingDomainB: BorrowedStructure<Ring>,
425    RingRangeB: BorrowedStructure<Ring>,
426>
427    FreeModuleFiniteNumberedBasisLinearTransformation<
428        Ring,
429        RingB,
430        RingDomainB,
431        RingRangeB,
432        true,
433        true,
434    >
435{
436    pub fn construct_bijective(
437        ring: RingB,
438        domain: FinitelyFreeModuleStructure<Ring, RingDomainB>,
439        range: FinitelyFreeModuleStructure<Ring, RingRangeB>,
440        basis_image: impl Fn(usize) -> Vec<Ring::Set>,
441    ) -> Self {
442        Self::construct_impl(ring, domain, range, basis_image)
443    }
444}
445
446impl<
447    Ring: RingSignature,
448    RingB: BorrowedStructure<Ring>,
449    RingDomainB: BorrowedStructure<Ring>,
450    RingRangeB: BorrowedStructure<Ring>,
451    const INJECTIVE: bool,
452    const SURJECTIVE: bool,
453>
454    Morphism<
455        FinitelyFreeModuleStructure<Ring, RingDomainB>,
456        FinitelyFreeModuleStructure<Ring, RingRangeB>,
457    >
458    for FreeModuleFiniteNumberedBasisLinearTransformation<
459        Ring,
460        RingB,
461        RingDomainB,
462        RingRangeB,
463        INJECTIVE,
464        SURJECTIVE,
465    >
466{
467    fn domain(&self) -> &FinitelyFreeModuleStructure<Ring, RingDomainB> {
468        &self.domain
469    }
470
471    fn range(&self) -> &FinitelyFreeModuleStructure<Ring, RingRangeB> {
472        &self.range
473    }
474}
475
476impl<
477    Ring: RingSignature,
478    RingB: BorrowedStructure<Ring>,
479    RingDomainB: BorrowedStructure<Ring>,
480    RingRangeB: BorrowedStructure<Ring>,
481    const INJECTIVE: bool,
482    const SURJECTIVE: bool,
483>
484    Function<
485        FinitelyFreeModuleStructure<Ring, RingDomainB>,
486        FinitelyFreeModuleStructure<Ring, RingRangeB>,
487    >
488    for FreeModuleFiniteNumberedBasisLinearTransformation<
489        Ring,
490        RingB,
491        RingDomainB,
492        RingRangeB,
493        INJECTIVE,
494        SURJECTIVE,
495    >
496{
497    fn image(&self, x: &Vec<Ring::Set>) -> Vec<Ring::Set> {
498        self.range.from_col(
499            &MatrixStructure::new(self.ring.clone())
500                .mul(&self.matrix, &self.domain.to_col(x))
501                .unwrap(),
502        )
503    }
504}
505
506impl<
507    Ring: ReducedHermiteAlgorithmSignature,
508    RingB: BorrowedStructure<Ring>,
509    RingDomainB: BorrowedStructure<Ring>,
510    RingRangeB: BorrowedStructure<Ring>,
511    const SURJECTIVE: bool,
512>
513    InjectiveFunction<
514        FinitelyFreeModuleStructure<Ring, RingDomainB>,
515        FinitelyFreeModuleStructure<Ring, RingRangeB>,
516    >
517    for FreeModuleFiniteNumberedBasisLinearTransformation<
518        Ring,
519        RingB,
520        RingDomainB,
521        RingRangeB,
522        true,
523        SURJECTIVE,
524    >
525{
526    fn try_preimage(&self, y: &Vec<Ring::Set>) -> Option<Vec<Ring::Set>> {
527        MatrixStructure::new(self.ring.clone()).col_solve(self.matrix.clone(), y)
528    }
529}
530
531impl<
532    Ring: ReducedHermiteAlgorithmSignature,
533    RingB: BorrowedStructure<Ring>,
534    RingDomainB: BorrowedStructure<Ring>,
535    RingRangeB: BorrowedStructure<Ring>,
536>
537    BijectiveFunction<
538        FinitelyFreeModuleStructure<Ring, RingDomainB>,
539        FinitelyFreeModuleStructure<Ring, RingRangeB>,
540    >
541    for FreeModuleFiniteNumberedBasisLinearTransformation<
542        Ring,
543        RingB,
544        RingDomainB,
545        RingRangeB,
546        true,
547        true,
548    >
549{
550    fn preimage(&self, y: &Vec<Ring::Set>) -> Vec<Ring::Set> {
551        self.try_preimage(y).unwrap()
552    }
553}
554
555#[cfg(test)]
556mod tests {
557    use super::{FreeModuleFiniteNumberedBasisLinearTransformation, *};
558    use algebraeon_nzq::Integer;
559
560    #[test]
561    fn test_finite_rank_modules() {
562        let m = FinitelyFreeModuleStructure::new(Integer::structure(), 3);
563
564        let a = m.basis_element(0);
565        let b = m.basis_element(1);
566        let c = m.basis_element(2);
567
568        assert_eq!(
569            m.add(&m.neg(&b), &m.add(&a, &b)),
570            vec![Integer::from(1), Integer::from(0), Integer::from(0)]
571        );
572
573        assert_eq!(
574            m.add(&m.add(&a, &b), &m.add(&b, &c)),
575            vec![Integer::from(1), Integer::from(2), Integer::from(1)]
576        );
577
578        assert_eq!(
579            m.scalar_mul(&a, &5.into()),
580            vec![Integer::from(5), Integer::from(0), Integer::from(0)]
581        );
582
583        assert_eq!(m.basis_vecs(), vec![a, b, c]);
584    }
585
586    #[test]
587    fn test_finite_rank_modules_linear_transformation() {
588        let m = FinitelyFreeModuleStructure::new(Integer::structure(), 2);
589        let n = FinitelyFreeModuleStructure::new(Integer::structure(), 5);
590
591        let t = FreeModuleFiniteNumberedBasisLinearTransformation::construct_injective(
592            Integer::structure(),
593            m.clone(),
594            n.clone(),
595            |i| {
596                if i == 0 {
597                    vec![0, 2, 3, -4, 1]
598                        .into_iter()
599                        .map(Integer::from)
600                        .collect()
601                } else if i == 1 {
602                    vec![1, 2, 3, 2, 1].into_iter().map(Integer::from).collect()
603                } else {
604                    unreachable!()
605                }
606            },
607        );
608
609        assert_eq!(
610            t.image(&vec![Integer::from(1), Integer::from(2)]),
611            vec![2, 6, 9, 0, 3]
612                .into_iter()
613                .map(Integer::from)
614                .collect::<Vec<_>>()
615        );
616    }
617}
algebraeon_rings/module/finitely_free_module.rs

algebraeon_rings/module/
finitely_free_module.rs
