Metamath Proof Explorer


Theorem pmatcoe1fsupp

Description: For a polynomial matrix there is an upper bound for the coefficients of all the polynomials being not 0. (Contributed by AV, 3-Oct-2019) (Proof shortened by AV, 28-Nov-2019)

Ref Expression
Hypotheses pmatcoe1fsupp.p ⊢ P = Poly 1 ⁡ R
pmatcoe1fsupp.c ⊢ C = N Mat P
pmatcoe1fsupp.b ⊢ B = Base C
pmatcoe1fsupp.0 ⊢ 0 ˙ = 0 R
Assertion pmatcoe1fsupp ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → ∃ s ∈ ℕ 0 ∀ x ∈ ℕ 0 s < x → ∀ i ∈ N ∀ j ∈ N coe 1 ⁡ i M j ⁡ x = 0 ˙

Proof

Step Hyp Ref Expression
1 pmatcoe1fsupp.p ⊢ P = Poly 1 ⁡ R
2 pmatcoe1fsupp.c ⊢ C = N Mat P
3 pmatcoe1fsupp.b ⊢ B = Base C
4 pmatcoe1fsupp.0 ⊢ 0 ˙ = 0 R
5 ssrab2 ⊢ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ⊆ Base R ℕ 0
6 5 a1i ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ⊆ Base R ℕ 0
7 6 olcd ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ⊆ Base R ℕ 0 ∨ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ⊆ Base R ℕ 0
8 inss ⊢ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ⊆ Base R ℕ 0 ∨ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ⊆ Base R ℕ 0 → ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ⊆ Base R ℕ 0
9 7 8 syl ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ⊆ Base R ℕ 0
10 xpfi ⊢ N ∈ Fin ∧ N ∈ Fin → N × N ∈ Fin
11 10 anidms ⊢ N ∈ Fin → N × N ∈ Fin
12 snfi ⊢ coe 1 ⁡ M ⁡ u ∈ Fin
13 12 a1i ⊢ N ∈ Fin ∧ u ∈ N × N → coe 1 ⁡ M ⁡ u ∈ Fin
14 13 ralrimiva ⊢ N ∈ Fin → ∀ u ∈ N × N coe 1 ⁡ M ⁡ u ∈ Fin
15 11 14 jca ⊢ N ∈ Fin → N × N ∈ Fin ∧ ∀ u ∈ N × N coe 1 ⁡ M ⁡ u ∈ Fin
16 15 3ad2ant1 ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → N × N ∈ Fin ∧ ∀ u ∈ N × N coe 1 ⁡ M ⁡ u ∈ Fin
17 iunfi ⊢ N × N ∈ Fin ∧ ∀ u ∈ N × N coe 1 ⁡ M ⁡ u ∈ Fin → ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∈ Fin
18 infi ⊢ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∈ Fin → ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∈ Fin
19 16 17 18 3syl ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∈ Fin
20 fvex ⊢ 0 R ∈ V
21 4 20 eqeltri ⊢ 0 ˙ ∈ V
22 21 a1i ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → 0 ˙ ∈ V
23 elin ⊢ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ↔ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∧ w ∈ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v
24 breq1 ⊢ v = w → finSupp 0 ˙⁡ v ↔ finSupp 0 ˙⁡ w
25 24 elrab ⊢ w ∈ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ↔ w ∈ Base R ℕ 0 ∧ finSupp 0 ˙⁡ w
26 25 simprbi ⊢ w ∈ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v → finSupp 0 ˙⁡ w
27 23 26 simplbiim ⊢ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v → finSupp 0 ˙⁡ w
28 27 rgen ⊢ ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v finSupp 0 ˙⁡ w
29 28 a1i ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v finSupp 0 ˙⁡ w
30 fsuppmapnn0fiub0 ⊢ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ⊆ Base R ℕ 0 ∧ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∈ Fin ∧ 0 ˙ ∈ V → ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v finSupp 0 ˙⁡ w → ∃ s ∈ ℕ 0 ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙
31 30 imp ⊢ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ⊆ Base R ℕ 0 ∧ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∈ Fin ∧ 0 ˙ ∈ V ∧ ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v finSupp 0 ˙⁡ w → ∃ s ∈ ℕ 0 ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙
32 9 19 22 29 31 syl31anc ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → ∃ s ∈ ℕ 0 ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙
33 opelxpi ⊢ i ∈ N ∧ j ∈ N → i j ∈ N × N
34 df-ov ⊢ i M j = M ⁡ i j
35 34 fveq2i ⊢ coe 1 ⁡ i M j = coe 1 ⁡ M ⁡ i j
36 fvex ⊢ coe 1 ⁡ M ⁡ i j ∈ V
37 36 snid ⊢ coe 1 ⁡ M ⁡ i j ∈ coe 1 ⁡ M ⁡ i j
38 35 37 eqeltri ⊢ coe 1 ⁡ i M j ∈ coe 1 ⁡ M ⁡ i j
39 38 a1i ⊢ i ∈ N ∧ j ∈ N → coe 1 ⁡ i M j ∈ coe 1 ⁡ M ⁡ i j
40 2fveq3 ⊢ u = i j → coe 1 ⁡ M ⁡ u = coe 1 ⁡ M ⁡ i j
41 40 sneqd ⊢ u = i j → coe 1 ⁡ M ⁡ u = coe 1 ⁡ M ⁡ i j
42 41 eliuni ⊢ i j ∈ N × N ∧ coe 1 ⁡ i M j ∈ coe 1 ⁡ M ⁡ i j → coe 1 ⁡ i M j ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u
43 33 39 42 syl2anc ⊢ i ∈ N ∧ j ∈ N → coe 1 ⁡ i M j ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u
44 43 adantl ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → coe 1 ⁡ i M j ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u
45 eqid ⊢ Base P = Base P
46 simprl ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → i ∈ N
47 simprr ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → j ∈ N
48 3 eleq2i ⊢ M ∈ B ↔ M ∈ Base C
49 48 biimpi ⊢ M ∈ B → M ∈ Base C
50 49 3ad2ant3 ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → M ∈ Base C
51 50 ad3antrrr ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → M ∈ Base C
52 51 3 eleqtrrdi ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → M ∈ B
53 2 45 3 46 47 52 matecld ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → i M j ∈ Base P
54 eqid ⊢ coe 1 ⁡ i M j = coe 1 ⁡ i M j
55 eqid ⊢ 0 R = 0 R
56 eqid ⊢ Base R = Base R
57 54 45 1 55 56 coe1fsupp ⊢ i M j ∈ Base P → coe 1 ⁡ i M j ∈ v ∈ Base R ℕ 0 | finSupp 0 R⁡ v
58 53 57 syl ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → coe 1 ⁡ i M j ∈ v ∈ Base R ℕ 0 | finSupp 0 R⁡ v
59 4 a1i ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → 0 ˙ = 0 R
60 59 breq2d ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → finSupp 0 ˙⁡ v ↔ finSupp 0 R⁡ v
61 60 rabbidv ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v = v ∈ Base R ℕ 0 | finSupp 0 R⁡ v
62 61 eleq2d ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → coe 1 ⁡ i M j ∈ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ↔ coe 1 ⁡ i M j ∈ v ∈ Base R ℕ 0 | finSupp 0 R⁡ v
63 62 ad3antrrr ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → coe 1 ⁡ i M j ∈ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ↔ coe 1 ⁡ i M j ∈ v ∈ Base R ℕ 0 | finSupp 0 R⁡ v
64 58 63 mpbird ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → coe 1 ⁡ i M j ∈ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v
65 44 64 elind ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → coe 1 ⁡ i M j ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v
66 simplr ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → x ∈ ℕ 0
67 fveq1 ⊢ w = coe 1 ⁡ i M j → w ⁡ z = coe 1 ⁡ i M j ⁡ z
68 67 eqeq1d ⊢ w = coe 1 ⁡ i M j → w ⁡ z = 0 ˙ ↔ coe 1 ⁡ i M j ⁡ z = 0 ˙
69 68 imbi2d ⊢ w = coe 1 ⁡ i M j → s < z → w ⁡ z = 0 ˙ ↔ s < z → coe 1 ⁡ i M j ⁡ z = 0 ˙
70 breq2 ⊢ z = x → s < z ↔ s < x
71 fveqeq2 ⊢ z = x → coe 1 ⁡ i M j ⁡ z = 0 ˙ ↔ coe 1 ⁡ i M j ⁡ x = 0 ˙
72 70 71 imbi12d ⊢ z = x → s < z → coe 1 ⁡ i M j ⁡ z = 0 ˙ ↔ s < x → coe 1 ⁡ i M j ⁡ x = 0 ˙
73 69 72 rspc2v ⊢ coe 1 ⁡ i M j ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∧ x ∈ ℕ 0 → ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ → s < x → coe 1 ⁡ i M j ⁡ x = 0 ˙
74 65 66 73 syl2anc ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 ∧ i ∈ N ∧ j ∈ N → ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ → s < x → coe 1 ⁡ i M j ⁡ x = 0 ˙
75 74 ex ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 → i ∈ N ∧ j ∈ N → ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ → s < x → coe 1 ⁡ i M j ⁡ x = 0 ˙
76 75 com23 ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ x ∈ ℕ 0 → ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ → i ∈ N ∧ j ∈ N → s < x → coe 1 ⁡ i M j ⁡ x = 0 ˙
77 76 impancom ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ → x ∈ ℕ 0 → i ∈ N ∧ j ∈ N → s < x → coe 1 ⁡ i M j ⁡ x = 0 ˙
78 77 imp ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ ∧ x ∈ ℕ 0 → i ∈ N ∧ j ∈ N → s < x → coe 1 ⁡ i M j ⁡ x = 0 ˙
79 78 com23 ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ ∧ x ∈ ℕ 0 → s < x → i ∈ N ∧ j ∈ N → coe 1 ⁡ i M j ⁡ x = 0 ˙
80 79 ralrimdvv ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ ∧ x ∈ ℕ 0 → s < x → ∀ i ∈ N ∀ j ∈ N coe 1 ⁡ i M j ⁡ x = 0 ˙
81 80 ralrimiva ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 ∧ ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ → ∀ x ∈ ℕ 0 s < x → ∀ i ∈ N ∀ j ∈ N coe 1 ⁡ i M j ⁡ x = 0 ˙
82 81 ex ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B ∧ s ∈ ℕ 0 → ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ → ∀ x ∈ ℕ 0 s < x → ∀ i ∈ N ∀ j ∈ N coe 1 ⁡ i M j ⁡ x = 0 ˙
83 82 reximdva ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → ∃ s ∈ ℕ 0 ∀ w ∈ ⋃ u ∈ N × N coe 1 ⁡ M ⁡ u ∩ v ∈ Base R ℕ 0 | finSupp 0 ˙⁡ v ∀ z ∈ ℕ 0 s < z → w ⁡ z = 0 ˙ → ∃ s ∈ ℕ 0 ∀ x ∈ ℕ 0 s < x → ∀ i ∈ N ∀ j ∈ N coe 1 ⁡ i M j ⁡ x = 0 ˙
84 32 83 mpd ⊢ N ∈ Fin ∧ R ∈ Ring ∧ M ∈ B → ∃ s ∈ ℕ 0 ∀ x ∈ ℕ 0 s < x → ∀ i ∈ N ∀ j ∈ N coe 1 ⁡ i M j ⁡ x = 0 ˙