Mixing
Using $bar{A}$ ($A$ modulo $2$) to prove that $A$ is invertible
Following this website, https://yutsumura.com/how-to-prove-a-matrix-is-nonsingular-in-10-seconds/:
Let $bar{A}$ be the matrix whose $(i,j)$-entry is the $(i,j)$-entry of $A$ modulo $2$. That is
$bar{A}=begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
end{bmatrix}$
Since $det(A)$ is a polynomial of entries of $A$, we have
$$det(A)=det(bar{A}) (text{mod} 2)= 1$$
I cannot see how we get the equality $det(A)=det(bar{A}) (text{mod} 2)$ just because $det(A)$ is a polynomial of entries of $A$.
linear-algebra matrices polynomials modular-arithmetic determinant
asked Dec 31 '18 at 17:55
PermianPermian
2,1961135
add a comment |
Following this website, https://yutsumura.com/how-to-prove-a-matrix-is-nonsingular-in-10-seconds/:
Let $bar{A}$ be the matrix whose $(i,j)$-entry is the $(i,j)$-entry of $A$ modulo $2$. That is
$bar{A}=begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
end{bmatrix}$
Since $det(A)$ is a polynomial of entries of $A$, we have
$$det(A)=det(bar{A}) (text{mod} 2)= 1$$
I cannot see how we get the equality $det(A)=det(bar{A}) (text{mod} 2)$ just because $det(A)$ is a polynomial of entries of $A$.
linear-algebra matrices polynomials modular-arithmetic determinant
asked Dec 31 '18 at 17:55
PermianPermian
2,1961135
"$det(A)=det(bar{A}) (text{mod} 2)$" is nonsense. What is meant is: The residue class of $detleft(Aright)$ modulo $2$ is $detleft(overline{A}right) = 1$.
– darij grinberg
Dec 31 '18 at 18:27
I dont understand how this is so hard to understand!
– Permian
Dec 31 '18 at 18:37
Ideally I would like as simple an answer as possible
– Permian
Dec 31 '18 at 21:51
add a comment |
Following this website, https://yutsumura.com/how-to-prove-a-matrix-is-nonsingular-in-10-seconds/:
Let $bar{A}$ be the matrix whose $(i,j)$-entry is the $(i,j)$-entry of $A$ modulo $2$. That is
$bar{A}=begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
end{bmatrix}$
Since $det(A)$ is a polynomial of entries of $A$, we have
$$det(A)=det(bar{A}) (text{mod} 2)= 1$$
I cannot see how we get the equality $det(A)=det(bar{A}) (text{mod} 2)$ just because $det(A)$ is a polynomial of entries of $A$.
linear-algebra matrices polynomials modular-arithmetic determinant
asked Dec 31 '18 at 17:55
PermianPermian
2,1961135
Following this website, https://yutsumura.com/how-to-prove-a-matrix-is-nonsingular-in-10-seconds/:
Let $bar{A}$ be the matrix whose $(i,j)$-entry is the $(i,j)$-entry of $A$ modulo $2$. That is
$bar{A}=begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
end{bmatrix}$
Since $det(A)$ is a polynomial of entries of $A$, we have
$$det(A)=det(bar{A}) (text{mod} 2)= 1$$
I cannot see how we get the equality $det(A)=det(bar{A}) (text{mod} 2)$ just because $det(A)$ is a polynomial of entries of $A$.
linear-algebra matrices polynomials modular-arithmetic determinant
linear-algebra matrices polynomials modular-arithmetic determinant
asked Dec 31 '18 at 17:55
PermianPermian
2,1961135
asked Dec 31 '18 at 17:55
PermianPermian
2,1961135
edited Dec 31 '18 at 18:03
Permian
asked Dec 31 '18 at 17:55
PermianPermian
2,1961135
asked Dec 31 '18 at 17:55
PermianPermian
2,1961135
asked Dec 31 '18 at 17:55
PermianPermian
2,1961135
2,1961135
"$det(A)=det(bar{A}) (text{mod} 2)$" is nonsense. What is meant is: The residue class of $detleft(Aright)$ modulo $2$ is $detleft(overline{A}right) = 1$.
– darij grinberg
Dec 31 '18 at 18:27
I dont understand how this is so hard to understand!
– Permian
Dec 31 '18 at 18:37
Ideally I would like as simple an answer as possible
– Permian
Dec 31 '18 at 21:51
add a comment |
"$det(A)=det(bar{A}) (text{mod} 2)$" is nonsense. What is meant is: The residue class of $detleft(Aright)$ modulo $2$ is $detleft(overline{A}right) = 1$.
– darij grinberg
Dec 31 '18 at 18:27
I dont understand how this is so hard to understand!
– Permian
Dec 31 '18 at 18:37
Ideally I would like as simple an answer as possible
– Permian
Dec 31 '18 at 21:51
"$det(A)=det(bar{A}) (text{mod} 2)$" is nonsense. What is meant is: The residue class of $detleft(Aright)$ modulo $2$ is $detleft(overline{A}right) = 1$.
– darij grinberg
Dec 31 '18 at 18:27
"$det(A)=det(bar{A}) (text{mod} 2)$" is nonsense. What is meant is: The residue class of $detleft(Aright)$ modulo $2$ is $detleft(overline{A}right) = 1$.
– darij grinberg
Dec 31 '18 at 18:27
I dont understand how this is so hard to understand!
– Permian
Dec 31 '18 at 18:37
I dont understand how this is so hard to understand!
– Permian
Dec 31 '18 at 18:37
Ideally I would like as simple an answer as possible
– Permian
Dec 31 '18 at 21:51
Ideally I would like as simple an answer as possible
– Permian
Dec 31 '18 at 21:51
add a comment |
5 Answers
5
active
oldest
votes
For an integer $n$ ($2$ in your case) the application:
$$begin{array}{l|rcl}
varphi : & mathbb Z & longrightarrow & mathbb Z_n\
& x & longmapsto & overline{x}
end{array}$$
is a ring homomorphism.
Hence for a multivariate polynomial $P(x_1, dots, x_m)$ you have $varphi(P) = overline{P}$ where $overline{P}$ is the polynomial obtained by taking the modulus of all coefficients.
Now $$det A = sum_{sigma in mathcal S_n} (-1)^{epsilon(sigma)} a_{1 sigma(1)} dots a_{n sigma(n)}$$ is a multivariate polynomial of the coefficients of $A$. Therefore the conclusion. See Wikipedia - determinant for above formula on the determinant.
answered Dec 31 '18 at 18:08
mathcounterexamples.netmathcounterexamples.net
25.3k21953
add a comment |
That is because you have a matrix in $mathcal M_n(bf Z)$ and the canonical map
begin{align}
pi:mathbf Z&longrightarrow mathbf Z/2mathbf Z \
n&longmapsto nbmod 2
end{align}
is a ring homomorphism, i.e. it is compatible with addition and multiplication.
answered Dec 31 '18 at 18:02
BernardBernard
118k639112
How does this link to the determinant?
– Permian
Dec 31 '18 at 18:03
1
A determinant is a polynomial in $n^2$ variables $f(a_{ij});(1le i,jle n)$ which involves a sole operations additions and multiplications. For any such polynomial, $;f(a_ {ij}bmod 2)=f(a_ {ij})bmod 2$.
– Bernard
Dec 31 '18 at 18:09
"i.e. it is compatible with addition and multiplication." ...so?
– Permian
Dec 31 '18 at 22:59
My previous comment has a formula for evaluating a polynomial mod. $2$. By cpntrapositice, there results that if such a polynomial, with the variables evaluated mod. 2$, is non-zero, the value of the polynomial itself is non-zero mod. $2$, hence this value is non-zero. Isn't it clear?
– Bernard
Dec 31 '18 at 23:09
add a comment |
If $x equiv y pmod N$ and if ${a_i}_{i=0}^n subseteq mathbb Z$, then
$$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$$
An example should help.
Let $A = left[begin{array}{c} 11 & 13 \ 17 & 19end{array}right]$.
Then $det A = 11 times 19 - 13 times 17 = -12 equiv 2 pmod 7$
Also $bar A = A pmod 7 =
left[begin{array}{c}
4 & 6 \
3 & 5
end{array}right]$
and $det bar A =4 times 5 - 6 times 3
equiv 11 times 19 - 13 times 17
equiv det A pmod 7$
answered Dec 31 '18 at 18:03
steven gregorysteven gregory
17.7k32257
How does this link to the determinant???
– Permian
Dec 31 '18 at 18:03
See @matcounterexamples answer for how it links.
– steven gregory
Dec 31 '18 at 18:11
$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$ is not clear to me. You see I would have the powers would have messed up the relationship
– Permian
Dec 31 '18 at 21:27
I get the example but I still cant see this in general
– Permian
Dec 31 '18 at 22:09
add a comment |
If $,f(x,y),$ is a polynomial with integer coefficients then by the polynomial congruence rule
$$bmod 2!:, f(m,n),equiv, f(overbrace{mbmod 2}^{large overline{m}},, overbrace{nbmod 2}^{largeoverline{n}})qquad $$
So $,f(m,n) = 0,Rightarrow, f(bar m,bar n) equiv 0pmod{!2} $ so contra+, $ f(bar m,bar n) notequiv 0pmod{!2},Rightarrow, f(m,n)neq 0$
i.e. any root $,(m,n),$ of $f$ persists as a root $!bmod 2.,$ OP is the special case when $f$ is the determinant function - which is indeed a polynomial function of its entries (with integer coefficients). Concretely
$$d = left|begin{array}{}color{#c00}{11} & color{#0a0}{22}\ color{#0a0}{33} & color{#c00}{55}end{array}right| = left{begin{align}&f(11,22,33,55) = color{#c00}{11(55)}!-!color{#0a0}{22(33)}\
equiv &f( 1, 0, 1, 1) equiv color{#c00}{ 1( 1)}-color{#0a0}{0( 1)}equiv 1!!!pmod{!2}end{align}right.qquad$$
therefore $,dequiv 1pmod{!2},,$ i.e. $,d,$ is odd, so $,dneq 0.$
Remark $ $ The same works for any modulus $,m,,$ e.g. we could use $,m = 9,$ ("casting out nines") exactly as above (or more generally as a check of any such polynomial computation), or we could compare unit digits $bmod m!=!10!: ,dequiv color{#c00}{1(5)}-color{#0a0}{2(3)}equiv -1 $ so $,dneq 0.$
For motivation you might find instructive this post on the parity root test for polynomials. Such parity arguments are a prototypical way of solving ring (algebraic) problems via information gleaned from (simpler) modular images (an algebraic way of "dividing and conquering").
answered Dec 31 '18 at 18:25
Bill DubuqueBill Dubuque
209k29190631
A simpler form in case you don't know about quotient rings.
– Bill Dubuque
Dec 31 '18 at 18:28
add a comment |
Here is perhaps the simplest answer to the specific question, avoiding the use of ring homomorphisms and residue classes. (Note: You should learn about ring homomorphisms and residue classes if you want to get anywhere in abstract algebra; you won't always be able to work as concretely as below.)
Fix a nonnegative integer $n$. We let $left[nright]$ denote the set $left{1,2,ldots,nright}$.
Lemma 1. Let $A = left(a_{i,j}right)_{i, j in left[nright]}$ and $B = left(b_{i,j}right)_{i, j in left[nright]}$ be two $ntimes n$-matrices of integers. Let $N$ be an integer. Assume that
begin{equation}
a_{i,j} equiv b_{i,j} mod N
label{darij.eq.l1.1}
tag{1}
end{equation}
for all $i, j in left[nright]$. Then, $det A equiv det B mod N$.
Proof of Lemma 1. The Leibniz formula for determinants yields $det A = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n a_{i, sigmaleft(iright)}$ and $det B = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}$ (where $S_n$ denotes the set of all permutations of $left[nright]$, and where $left(-1right)^{sigma}$ denotes the sign of a permutation $sigma$). Thus,
begin{align}
det A
& = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n underbrace{a_{i, sigmaleft(iright)}}_{substack{equiv b_{i, sigmaleft(iright)} mod N \ left(text{by eqref{darij.eq.l1.1}}right)}} \
& equiv sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}
= det B mod N
end{align}
(here, we tacitly used the fact that everything in our expressions is an integer, and that congruences modulo $N$ can be multiplied).
This proves Lemma 1. $blacksquare$
Corollary 2. Let $A$ be an $n times n$-matrix of integers such that all diagonal entries of $A$ are odd and all non-diagonal entries of $A$ are even. Then, $det A$ is odd.
Proof of Corollary 2. Write the matrix $A$ as $A = left(a_{i,j}right)_{i, j in left[nright]}$. Also, write the identity $ntimes n$-matrix $I_n$ as $I_n = left(b_{i,j}right)_{i, j in left[nright]}$. Then, it is easy to prove the congruence $a_{i,j} equiv b_{i,j} mod 2$ for all $i, j in left[nright]$. (Indeed, if $i = j$, then $a_{i,j}$ is a diagonal entry of $A$, whereas $b_{i,j}$ is a diagonal entry of $I_n$ and thus equals $1$; hence, this congruence says that all diagonal entries of $A$ are odd. This is true by assumption. On the other hand, if $i neq j$, then $a_{i,j}$ is a non-diagonal entry of $A$, whereas $b_{i,j}$ is a non-diagonal entry of $I_n$ and thus equals $0$; hence, this congruence says that all non-diagonal entries of $A$ are even. This is again true by assumption. Thus, the congruence holds in both cases $i = j$ and $i neq j$.)
Thus, Lemma 1 (applied to $N=2$ and $B=I_n$) yields $det A equiv detleft(I_nright) = 1 mod 2$. In other words, $det A$ is odd. $blacksquare$
Corollary 2 can be directly applied to your matrix $A$.
answered Dec 31 '18 at 22:33
darij grinbergdarij grinberg
10.4k33062
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3057908%2fusing-bara-a-modulo-2-to-prove-that-a-is-invertible%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
For an integer $n$ ($2$ in your case) the application:
$$begin{array}{l|rcl}
varphi : & mathbb Z & longrightarrow & mathbb Z_n\
& x & longmapsto & overline{x}
end{array}$$
is a ring homomorphism.
Hence for a multivariate polynomial $P(x_1, dots, x_m)$ you have $varphi(P) = overline{P}$ where $overline{P}$ is the polynomial obtained by taking the modulus of all coefficients.
Now $$det A = sum_{sigma in mathcal S_n} (-1)^{epsilon(sigma)} a_{1 sigma(1)} dots a_{n sigma(n)}$$ is a multivariate polynomial of the coefficients of $A$. Therefore the conclusion. See Wikipedia - determinant for above formula on the determinant.
answered Dec 31 '18 at 18:08
mathcounterexamples.netmathcounterexamples.net
25.3k21953
add a comment |
For an integer $n$ ($2$ in your case) the application:
$$begin{array}{l|rcl}
varphi : & mathbb Z & longrightarrow & mathbb Z_n\
& x & longmapsto & overline{x}
end{array}$$
is a ring homomorphism.
Hence for a multivariate polynomial $P(x_1, dots, x_m)$ you have $varphi(P) = overline{P}$ where $overline{P}$ is the polynomial obtained by taking the modulus of all coefficients.
Now $$det A = sum_{sigma in mathcal S_n} (-1)^{epsilon(sigma)} a_{1 sigma(1)} dots a_{n sigma(n)}$$ is a multivariate polynomial of the coefficients of $A$. Therefore the conclusion. See Wikipedia - determinant for above formula on the determinant.
answered Dec 31 '18 at 18:08
mathcounterexamples.netmathcounterexamples.net
25.3k21953
add a comment |
For an integer $n$ ($2$ in your case) the application:
$$begin{array}{l|rcl}
varphi : & mathbb Z & longrightarrow & mathbb Z_n\
& x & longmapsto & overline{x}
end{array}$$
is a ring homomorphism.
Hence for a multivariate polynomial $P(x_1, dots, x_m)$ you have $varphi(P) = overline{P}$ where $overline{P}$ is the polynomial obtained by taking the modulus of all coefficients.
Now $$det A = sum_{sigma in mathcal S_n} (-1)^{epsilon(sigma)} a_{1 sigma(1)} dots a_{n sigma(n)}$$ is a multivariate polynomial of the coefficients of $A$. Therefore the conclusion. See Wikipedia - determinant for above formula on the determinant.
answered Dec 31 '18 at 18:08
mathcounterexamples.netmathcounterexamples.net
25.3k21953
For an integer $n$ ($2$ in your case) the application:
$$begin{array}{l|rcl}
varphi : & mathbb Z & longrightarrow & mathbb Z_n\
& x & longmapsto & overline{x}
end{array}$$
is a ring homomorphism.
Hence for a multivariate polynomial $P(x_1, dots, x_m)$ you have $varphi(P) = overline{P}$ where $overline{P}$ is the polynomial obtained by taking the modulus of all coefficients.
Now $$det A = sum_{sigma in mathcal S_n} (-1)^{epsilon(sigma)} a_{1 sigma(1)} dots a_{n sigma(n)}$$ is a multivariate polynomial of the coefficients of $A$. Therefore the conclusion. See Wikipedia - determinant for above formula on the determinant.
answered Dec 31 '18 at 18:08
mathcounterexamples.netmathcounterexamples.net
25.3k21953
edited Dec 31 '18 at 18:14
answered Dec 31 '18 at 18:08
mathcounterexamples.netmathcounterexamples.net
25.3k21953
answered Dec 31 '18 at 18:08
mathcounterexamples.netmathcounterexamples.net
25.3k21953
answered Dec 31 '18 at 18:08
mathcounterexamples.netmathcounterexamples.net
25.3k21953
25.3k21953
add a comment |
add a comment |
That is because you have a matrix in $mathcal M_n(bf Z)$ and the canonical map
begin{align}
pi:mathbf Z&longrightarrow mathbf Z/2mathbf Z \
n&longmapsto nbmod 2
end{align}
is a ring homomorphism, i.e. it is compatible with addition and multiplication.
answered Dec 31 '18 at 18:02
BernardBernard
118k639112
How does this link to the determinant?
– Permian
Dec 31 '18 at 18:03
1
A determinant is a polynomial in $n^2$ variables $f(a_{ij});(1le i,jle n)$ which involves a sole operations additions and multiplications. For any such polynomial, $;f(a_ {ij}bmod 2)=f(a_ {ij})bmod 2$.
– Bernard
Dec 31 '18 at 18:09
"i.e. it is compatible with addition and multiplication." ...so?
– Permian
Dec 31 '18 at 22:59
My previous comment has a formula for evaluating a polynomial mod. $2$. By cpntrapositice, there results that if such a polynomial, with the variables evaluated mod. 2$, is non-zero, the value of the polynomial itself is non-zero mod. $2$, hence this value is non-zero. Isn't it clear?
– Bernard
Dec 31 '18 at 23:09
add a comment |
That is because you have a matrix in $mathcal M_n(bf Z)$ and the canonical map
begin{align}
pi:mathbf Z&longrightarrow mathbf Z/2mathbf Z \
n&longmapsto nbmod 2
end{align}
is a ring homomorphism, i.e. it is compatible with addition and multiplication.
answered Dec 31 '18 at 18:02
BernardBernard
118k639112
How does this link to the determinant?
– Permian
Dec 31 '18 at 18:03
1
A determinant is a polynomial in $n^2$ variables $f(a_{ij});(1le i,jle n)$ which involves a sole operations additions and multiplications. For any such polynomial, $;f(a_ {ij}bmod 2)=f(a_ {ij})bmod 2$.
– Bernard
Dec 31 '18 at 18:09
"i.e. it is compatible with addition and multiplication." ...so?
– Permian
Dec 31 '18 at 22:59
My previous comment has a formula for evaluating a polynomial mod. $2$. By cpntrapositice, there results that if such a polynomial, with the variables evaluated mod. 2$, is non-zero, the value of the polynomial itself is non-zero mod. $2$, hence this value is non-zero. Isn't it clear?
– Bernard
Dec 31 '18 at 23:09
add a comment |
That is because you have a matrix in $mathcal M_n(bf Z)$ and the canonical map
begin{align}
pi:mathbf Z&longrightarrow mathbf Z/2mathbf Z \
n&longmapsto nbmod 2
end{align}
is a ring homomorphism, i.e. it is compatible with addition and multiplication.
answered Dec 31 '18 at 18:02
BernardBernard
118k639112
That is because you have a matrix in $mathcal M_n(bf Z)$ and the canonical map
begin{align}
pi:mathbf Z&longrightarrow mathbf Z/2mathbf Z \
n&longmapsto nbmod 2
end{align}
is a ring homomorphism, i.e. it is compatible with addition and multiplication.
answered Dec 31 '18 at 18:02
BernardBernard
118k639112
edited Dec 31 '18 at 19:15
answered Dec 31 '18 at 18:02
BernardBernard
118k639112
answered Dec 31 '18 at 18:02
BernardBernard
118k639112
answered Dec 31 '18 at 18:02
BernardBernard
118k639112
118k639112
How does this link to the determinant?
– Permian
Dec 31 '18 at 18:03
1
A determinant is a polynomial in $n^2$ variables $f(a_{ij});(1le i,jle n)$ which involves a sole operations additions and multiplications. For any such polynomial, $;f(a_ {ij}bmod 2)=f(a_ {ij})bmod 2$.
– Bernard
Dec 31 '18 at 18:09
"i.e. it is compatible with addition and multiplication." ...so?
– Permian
Dec 31 '18 at 22:59
My previous comment has a formula for evaluating a polynomial mod. $2$. By cpntrapositice, there results that if such a polynomial, with the variables evaluated mod. 2$, is non-zero, the value of the polynomial itself is non-zero mod. $2$, hence this value is non-zero. Isn't it clear?
– Bernard
Dec 31 '18 at 23:09
add a comment |
How does this link to the determinant?
– Permian
Dec 31 '18 at 18:03
1
A determinant is a polynomial in $n^2$ variables $f(a_{ij});(1le i,jle n)$ which involves a sole operations additions and multiplications. For any such polynomial, $;f(a_ {ij}bmod 2)=f(a_ {ij})bmod 2$.
– Bernard
Dec 31 '18 at 18:09
"i.e. it is compatible with addition and multiplication." ...so?
– Permian
Dec 31 '18 at 22:59
My previous comment has a formula for evaluating a polynomial mod. $2$. By cpntrapositice, there results that if such a polynomial, with the variables evaluated mod. 2$, is non-zero, the value of the polynomial itself is non-zero mod. $2$, hence this value is non-zero. Isn't it clear?
– Bernard
Dec 31 '18 at 23:09
How does this link to the determinant?
– Permian
Dec 31 '18 at 18:03
How does this link to the determinant?
– Permian
Dec 31 '18 at 18:03
1
1
A determinant is a polynomial in $n^2$ variables $f(a_{ij});(1le i,jle n)$ which involves a sole operations additions and multiplications. For any such polynomial, $;f(a_ {ij}bmod 2)=f(a_ {ij})bmod 2$.
– Bernard
Dec 31 '18 at 18:09
A determinant is a polynomial in $n^2$ variables $f(a_{ij});(1le i,jle n)$ which involves a sole operations additions and multiplications. For any such polynomial, $;f(a_ {ij}bmod 2)=f(a_ {ij})bmod 2$.
– Bernard
Dec 31 '18 at 18:09
"i.e. it is compatible with addition and multiplication." ...so?
– Permian
Dec 31 '18 at 22:59
"i.e. it is compatible with addition and multiplication." ...so?
– Permian
Dec 31 '18 at 22:59
My previous comment has a formula for evaluating a polynomial mod. $2$. By cpntrapositice, there results that if such a polynomial, with the variables evaluated mod. 2$, is non-zero, the value of the polynomial itself is non-zero mod. $2$, hence this value is non-zero. Isn't it clear?
– Bernard
Dec 31 '18 at 23:09
My previous comment has a formula for evaluating a polynomial mod. $2$. By cpntrapositice, there results that if such a polynomial, with the variables evaluated mod. 2$, is non-zero, the value of the polynomial itself is non-zero mod. $2$, hence this value is non-zero. Isn't it clear?
– Bernard
Dec 31 '18 at 23:09
add a comment |
If $x equiv y pmod N$ and if ${a_i}_{i=0}^n subseteq mathbb Z$, then
$$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$$
An example should help.
Let $A = left[begin{array}{c} 11 & 13 \ 17 & 19end{array}right]$.
Then $det A = 11 times 19 - 13 times 17 = -12 equiv 2 pmod 7$
Also $bar A = A pmod 7 =
left[begin{array}{c}
4 & 6 \
3 & 5
end{array}right]$
and $det bar A =4 times 5 - 6 times 3
equiv 11 times 19 - 13 times 17
equiv det A pmod 7$
answered Dec 31 '18 at 18:03
steven gregorysteven gregory
17.7k32257
How does this link to the determinant???
– Permian
Dec 31 '18 at 18:03
See @matcounterexamples answer for how it links.
– steven gregory
Dec 31 '18 at 18:11
$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$ is not clear to me. You see I would have the powers would have messed up the relationship
– Permian
Dec 31 '18 at 21:27
I get the example but I still cant see this in general
– Permian
Dec 31 '18 at 22:09
add a comment |
If $x equiv y pmod N$ and if ${a_i}_{i=0}^n subseteq mathbb Z$, then
$$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$$
An example should help.
Let $A = left[begin{array}{c} 11 & 13 \ 17 & 19end{array}right]$.
Then $det A = 11 times 19 - 13 times 17 = -12 equiv 2 pmod 7$
Also $bar A = A pmod 7 =
left[begin{array}{c}
4 & 6 \
3 & 5
end{array}right]$
and $det bar A =4 times 5 - 6 times 3
equiv 11 times 19 - 13 times 17
equiv det A pmod 7$
answered Dec 31 '18 at 18:03
steven gregorysteven gregory
17.7k32257
How does this link to the determinant???
– Permian
Dec 31 '18 at 18:03
See @matcounterexamples answer for how it links.
– steven gregory
Dec 31 '18 at 18:11
$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$ is not clear to me. You see I would have the powers would have messed up the relationship
– Permian
Dec 31 '18 at 21:27
I get the example but I still cant see this in general
– Permian
Dec 31 '18 at 22:09
add a comment |
If $x equiv y pmod N$ and if ${a_i}_{i=0}^n subseteq mathbb Z$, then
$$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$$
An example should help.
Let $A = left[begin{array}{c} 11 & 13 \ 17 & 19end{array}right]$.
Then $det A = 11 times 19 - 13 times 17 = -12 equiv 2 pmod 7$
Also $bar A = A pmod 7 =
left[begin{array}{c}
4 & 6 \
3 & 5
end{array}right]$
and $det bar A =4 times 5 - 6 times 3
equiv 11 times 19 - 13 times 17
equiv det A pmod 7$
answered Dec 31 '18 at 18:03
steven gregorysteven gregory
17.7k32257
If $x equiv y pmod N$ and if ${a_i}_{i=0}^n subseteq mathbb Z$, then
$$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$$
An example should help.
Let $A = left[begin{array}{c} 11 & 13 \ 17 & 19end{array}right]$.
Then $det A = 11 times 19 - 13 times 17 = -12 equiv 2 pmod 7$
Also $bar A = A pmod 7 =
left[begin{array}{c}
4 & 6 \
3 & 5
end{array}right]$
and $det bar A =4 times 5 - 6 times 3
equiv 11 times 19 - 13 times 17
equiv det A pmod 7$
answered Dec 31 '18 at 18:03
steven gregorysteven gregory
17.7k32257
edited Dec 31 '18 at 20:53
answered Dec 31 '18 at 18:03
steven gregorysteven gregory
17.7k32257
answered Dec 31 '18 at 18:03
steven gregorysteven gregory
17.7k32257
answered Dec 31 '18 at 18:03
steven gregorysteven gregory
17.7k32257
17.7k32257
How does this link to the determinant???
– Permian
Dec 31 '18 at 18:03
See @matcounterexamples answer for how it links.
– steven gregory
Dec 31 '18 at 18:11
$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$ is not clear to me. You see I would have the powers would have messed up the relationship
– Permian
Dec 31 '18 at 21:27
I get the example but I still cant see this in general
– Permian
Dec 31 '18 at 22:09
add a comment |
How does this link to the determinant???
– Permian
Dec 31 '18 at 18:03
See @matcounterexamples answer for how it links.
– steven gregory
Dec 31 '18 at 18:11
$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$ is not clear to me. You see I would have the powers would have messed up the relationship
– Permian
Dec 31 '18 at 21:27
I get the example but I still cant see this in general
– Permian
Dec 31 '18 at 22:09
How does this link to the determinant???
– Permian
Dec 31 '18 at 18:03
How does this link to the determinant???
– Permian
Dec 31 '18 at 18:03
See @matcounterexamples answer for how it links.
– steven gregory
Dec 31 '18 at 18:11
See @matcounterexamples answer for how it links.
– steven gregory
Dec 31 '18 at 18:11
$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$ is not clear to me. You see I would have the powers would have messed up the relationship
– Permian
Dec 31 '18 at 21:27
$sum_{i=0}^n a_i x^i equiv sum_{i=0}^n a_i y^i pmod N$ is not clear to me. You see I would have the powers would have messed up the relationship
– Permian
Dec 31 '18 at 21:27
I get the example but I still cant see this in general
– Permian
Dec 31 '18 at 22:09
I get the example but I still cant see this in general
– Permian
Dec 31 '18 at 22:09
add a comment |
If $,f(x,y),$ is a polynomial with integer coefficients then by the polynomial congruence rule
$$bmod 2!:, f(m,n),equiv, f(overbrace{mbmod 2}^{large overline{m}},, overbrace{nbmod 2}^{largeoverline{n}})qquad $$
So $,f(m,n) = 0,Rightarrow, f(bar m,bar n) equiv 0pmod{!2} $ so contra+, $ f(bar m,bar n) notequiv 0pmod{!2},Rightarrow, f(m,n)neq 0$
i.e. any root $,(m,n),$ of $f$ persists as a root $!bmod 2.,$ OP is the special case when $f$ is the determinant function - which is indeed a polynomial function of its entries (with integer coefficients). Concretely
$$d = left|begin{array}{}color{#c00}{11} & color{#0a0}{22}\ color{#0a0}{33} & color{#c00}{55}end{array}right| = left{begin{align}&f(11,22,33,55) = color{#c00}{11(55)}!-!color{#0a0}{22(33)}\
equiv &f( 1, 0, 1, 1) equiv color{#c00}{ 1( 1)}-color{#0a0}{0( 1)}equiv 1!!!pmod{!2}end{align}right.qquad$$
therefore $,dequiv 1pmod{!2},,$ i.e. $,d,$ is odd, so $,dneq 0.$
Remark $ $ The same works for any modulus $,m,,$ e.g. we could use $,m = 9,$ ("casting out nines") exactly as above (or more generally as a check of any such polynomial computation), or we could compare unit digits $bmod m!=!10!: ,dequiv color{#c00}{1(5)}-color{#0a0}{2(3)}equiv -1 $ so $,dneq 0.$
For motivation you might find instructive this post on the parity root test for polynomials. Such parity arguments are a prototypical way of solving ring (algebraic) problems via information gleaned from (simpler) modular images (an algebraic way of "dividing and conquering").
answered Dec 31 '18 at 18:25
Bill DubuqueBill Dubuque
209k29190631
A simpler form in case you don't know about quotient rings.
– Bill Dubuque
Dec 31 '18 at 18:28
add a comment |
If $,f(x,y),$ is a polynomial with integer coefficients then by the polynomial congruence rule
$$bmod 2!:, f(m,n),equiv, f(overbrace{mbmod 2}^{large overline{m}},, overbrace{nbmod 2}^{largeoverline{n}})qquad $$
So $,f(m,n) = 0,Rightarrow, f(bar m,bar n) equiv 0pmod{!2} $ so contra+, $ f(bar m,bar n) notequiv 0pmod{!2},Rightarrow, f(m,n)neq 0$
i.e. any root $,(m,n),$ of $f$ persists as a root $!bmod 2.,$ OP is the special case when $f$ is the determinant function - which is indeed a polynomial function of its entries (with integer coefficients). Concretely
$$d = left|begin{array}{}color{#c00}{11} & color{#0a0}{22}\ color{#0a0}{33} & color{#c00}{55}end{array}right| = left{begin{align}&f(11,22,33,55) = color{#c00}{11(55)}!-!color{#0a0}{22(33)}\
equiv &f( 1, 0, 1, 1) equiv color{#c00}{ 1( 1)}-color{#0a0}{0( 1)}equiv 1!!!pmod{!2}end{align}right.qquad$$
therefore $,dequiv 1pmod{!2},,$ i.e. $,d,$ is odd, so $,dneq 0.$
Remark $ $ The same works for any modulus $,m,,$ e.g. we could use $,m = 9,$ ("casting out nines") exactly as above (or more generally as a check of any such polynomial computation), or we could compare unit digits $bmod m!=!10!: ,dequiv color{#c00}{1(5)}-color{#0a0}{2(3)}equiv -1 $ so $,dneq 0.$
For motivation you might find instructive this post on the parity root test for polynomials. Such parity arguments are a prototypical way of solving ring (algebraic) problems via information gleaned from (simpler) modular images (an algebraic way of "dividing and conquering").
answered Dec 31 '18 at 18:25
Bill DubuqueBill Dubuque
209k29190631
A simpler form in case you don't know about quotient rings.
– Bill Dubuque
Dec 31 '18 at 18:28
add a comment |
If $,f(x,y),$ is a polynomial with integer coefficients then by the polynomial congruence rule
$$bmod 2!:, f(m,n),equiv, f(overbrace{mbmod 2}^{large overline{m}},, overbrace{nbmod 2}^{largeoverline{n}})qquad $$
So $,f(m,n) = 0,Rightarrow, f(bar m,bar n) equiv 0pmod{!2} $ so contra+, $ f(bar m,bar n) notequiv 0pmod{!2},Rightarrow, f(m,n)neq 0$
i.e. any root $,(m,n),$ of $f$ persists as a root $!bmod 2.,$ OP is the special case when $f$ is the determinant function - which is indeed a polynomial function of its entries (with integer coefficients). Concretely
$$d = left|begin{array}{}color{#c00}{11} & color{#0a0}{22}\ color{#0a0}{33} & color{#c00}{55}end{array}right| = left{begin{align}&f(11,22,33,55) = color{#c00}{11(55)}!-!color{#0a0}{22(33)}\
equiv &f( 1, 0, 1, 1) equiv color{#c00}{ 1( 1)}-color{#0a0}{0( 1)}equiv 1!!!pmod{!2}end{align}right.qquad$$
therefore $,dequiv 1pmod{!2},,$ i.e. $,d,$ is odd, so $,dneq 0.$
Remark $ $ The same works for any modulus $,m,,$ e.g. we could use $,m = 9,$ ("casting out nines") exactly as above (or more generally as a check of any such polynomial computation), or we could compare unit digits $bmod m!=!10!: ,dequiv color{#c00}{1(5)}-color{#0a0}{2(3)}equiv -1 $ so $,dneq 0.$
For motivation you might find instructive this post on the parity root test for polynomials. Such parity arguments are a prototypical way of solving ring (algebraic) problems via information gleaned from (simpler) modular images (an algebraic way of "dividing and conquering").
answered Dec 31 '18 at 18:25
Bill DubuqueBill Dubuque
209k29190631
If $,f(x,y),$ is a polynomial with integer coefficients then by the polynomial congruence rule
$$bmod 2!:, f(m,n),equiv, f(overbrace{mbmod 2}^{large overline{m}},, overbrace{nbmod 2}^{largeoverline{n}})qquad $$
So $,f(m,n) = 0,Rightarrow, f(bar m,bar n) equiv 0pmod{!2} $ so contra+, $ f(bar m,bar n) notequiv 0pmod{!2},Rightarrow, f(m,n)neq 0$
i.e. any root $,(m,n),$ of $f$ persists as a root $!bmod 2.,$ OP is the special case when $f$ is the determinant function - which is indeed a polynomial function of its entries (with integer coefficients). Concretely
$$d = left|begin{array}{}color{#c00}{11} & color{#0a0}{22}\ color{#0a0}{33} & color{#c00}{55}end{array}right| = left{begin{align}&f(11,22,33,55) = color{#c00}{11(55)}!-!color{#0a0}{22(33)}\
equiv &f( 1, 0, 1, 1) equiv color{#c00}{ 1( 1)}-color{#0a0}{0( 1)}equiv 1!!!pmod{!2}end{align}right.qquad$$
therefore $,dequiv 1pmod{!2},,$ i.e. $,d,$ is odd, so $,dneq 0.$
Remark $ $ The same works for any modulus $,m,,$ e.g. we could use $,m = 9,$ ("casting out nines") exactly as above (or more generally as a check of any such polynomial computation), or we could compare unit digits $bmod m!=!10!: ,dequiv color{#c00}{1(5)}-color{#0a0}{2(3)}equiv -1 $ so $,dneq 0.$
For motivation you might find instructive this post on the parity root test for polynomials. Such parity arguments are a prototypical way of solving ring (algebraic) problems via information gleaned from (simpler) modular images (an algebraic way of "dividing and conquering").
answered Dec 31 '18 at 18:25
Bill DubuqueBill Dubuque
209k29190631
edited Dec 31 '18 at 19:32
answered Dec 31 '18 at 18:25
Bill DubuqueBill Dubuque
209k29190631
answered Dec 31 '18 at 18:25
Bill DubuqueBill Dubuque
209k29190631
answered Dec 31 '18 at 18:25
Bill DubuqueBill Dubuque
209k29190631
209k29190631
A simpler form in case you don't know about quotient rings.
– Bill Dubuque
Dec 31 '18 at 18:28
add a comment |
A simpler form in case you don't know about quotient rings.
– Bill Dubuque
Dec 31 '18 at 18:28
A simpler form in case you don't know about quotient rings.
– Bill Dubuque
Dec 31 '18 at 18:28
A simpler form in case you don't know about quotient rings.
– Bill Dubuque
Dec 31 '18 at 18:28
add a comment |
Here is perhaps the simplest answer to the specific question, avoiding the use of ring homomorphisms and residue classes. (Note: You should learn about ring homomorphisms and residue classes if you want to get anywhere in abstract algebra; you won't always be able to work as concretely as below.)
Fix a nonnegative integer $n$. We let $left[nright]$ denote the set $left{1,2,ldots,nright}$.
Lemma 1. Let $A = left(a_{i,j}right)_{i, j in left[nright]}$ and $B = left(b_{i,j}right)_{i, j in left[nright]}$ be two $ntimes n$-matrices of integers. Let $N$ be an integer. Assume that
begin{equation}
a_{i,j} equiv b_{i,j} mod N
label{darij.eq.l1.1}
tag{1}
end{equation}
for all $i, j in left[nright]$. Then, $det A equiv det B mod N$.
Proof of Lemma 1. The Leibniz formula for determinants yields $det A = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n a_{i, sigmaleft(iright)}$ and $det B = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}$ (where $S_n$ denotes the set of all permutations of $left[nright]$, and where $left(-1right)^{sigma}$ denotes the sign of a permutation $sigma$). Thus,
begin{align}
det A
& = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n underbrace{a_{i, sigmaleft(iright)}}_{substack{equiv b_{i, sigmaleft(iright)} mod N \ left(text{by eqref{darij.eq.l1.1}}right)}} \
& equiv sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}
= det B mod N
end{align}
(here, we tacitly used the fact that everything in our expressions is an integer, and that congruences modulo $N$ can be multiplied).
This proves Lemma 1. $blacksquare$
Corollary 2. Let $A$ be an $n times n$-matrix of integers such that all diagonal entries of $A$ are odd and all non-diagonal entries of $A$ are even. Then, $det A$ is odd.
Proof of Corollary 2. Write the matrix $A$ as $A = left(a_{i,j}right)_{i, j in left[nright]}$. Also, write the identity $ntimes n$-matrix $I_n$ as $I_n = left(b_{i,j}right)_{i, j in left[nright]}$. Then, it is easy to prove the congruence $a_{i,j} equiv b_{i,j} mod 2$ for all $i, j in left[nright]$. (Indeed, if $i = j$, then $a_{i,j}$ is a diagonal entry of $A$, whereas $b_{i,j}$ is a diagonal entry of $I_n$ and thus equals $1$; hence, this congruence says that all diagonal entries of $A$ are odd. This is true by assumption. On the other hand, if $i neq j$, then $a_{i,j}$ is a non-diagonal entry of $A$, whereas $b_{i,j}$ is a non-diagonal entry of $I_n$ and thus equals $0$; hence, this congruence says that all non-diagonal entries of $A$ are even. This is again true by assumption. Thus, the congruence holds in both cases $i = j$ and $i neq j$.)
Thus, Lemma 1 (applied to $N=2$ and $B=I_n$) yields $det A equiv detleft(I_nright) = 1 mod 2$. In other words, $det A$ is odd. $blacksquare$
Corollary 2 can be directly applied to your matrix $A$.
answered Dec 31 '18 at 22:33
darij grinbergdarij grinberg
10.4k33062
add a comment |
Here is perhaps the simplest answer to the specific question, avoiding the use of ring homomorphisms and residue classes. (Note: You should learn about ring homomorphisms and residue classes if you want to get anywhere in abstract algebra; you won't always be able to work as concretely as below.)
Fix a nonnegative integer $n$. We let $left[nright]$ denote the set $left{1,2,ldots,nright}$.
Lemma 1. Let $A = left(a_{i,j}right)_{i, j in left[nright]}$ and $B = left(b_{i,j}right)_{i, j in left[nright]}$ be two $ntimes n$-matrices of integers. Let $N$ be an integer. Assume that
begin{equation}
a_{i,j} equiv b_{i,j} mod N
label{darij.eq.l1.1}
tag{1}
end{equation}
for all $i, j in left[nright]$. Then, $det A equiv det B mod N$.
Proof of Lemma 1. The Leibniz formula for determinants yields $det A = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n a_{i, sigmaleft(iright)}$ and $det B = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}$ (where $S_n$ denotes the set of all permutations of $left[nright]$, and where $left(-1right)^{sigma}$ denotes the sign of a permutation $sigma$). Thus,
begin{align}
det A
& = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n underbrace{a_{i, sigmaleft(iright)}}_{substack{equiv b_{i, sigmaleft(iright)} mod N \ left(text{by eqref{darij.eq.l1.1}}right)}} \
& equiv sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}
= det B mod N
end{align}
(here, we tacitly used the fact that everything in our expressions is an integer, and that congruences modulo $N$ can be multiplied).
This proves Lemma 1. $blacksquare$
Corollary 2. Let $A$ be an $n times n$-matrix of integers such that all diagonal entries of $A$ are odd and all non-diagonal entries of $A$ are even. Then, $det A$ is odd.
Proof of Corollary 2. Write the matrix $A$ as $A = left(a_{i,j}right)_{i, j in left[nright]}$. Also, write the identity $ntimes n$-matrix $I_n$ as $I_n = left(b_{i,j}right)_{i, j in left[nright]}$. Then, it is easy to prove the congruence $a_{i,j} equiv b_{i,j} mod 2$ for all $i, j in left[nright]$. (Indeed, if $i = j$, then $a_{i,j}$ is a diagonal entry of $A$, whereas $b_{i,j}$ is a diagonal entry of $I_n$ and thus equals $1$; hence, this congruence says that all diagonal entries of $A$ are odd. This is true by assumption. On the other hand, if $i neq j$, then $a_{i,j}$ is a non-diagonal entry of $A$, whereas $b_{i,j}$ is a non-diagonal entry of $I_n$ and thus equals $0$; hence, this congruence says that all non-diagonal entries of $A$ are even. This is again true by assumption. Thus, the congruence holds in both cases $i = j$ and $i neq j$.)
Thus, Lemma 1 (applied to $N=2$ and $B=I_n$) yields $det A equiv detleft(I_nright) = 1 mod 2$. In other words, $det A$ is odd. $blacksquare$
Corollary 2 can be directly applied to your matrix $A$.
answered Dec 31 '18 at 22:33
darij grinbergdarij grinberg
10.4k33062
add a comment |
Here is perhaps the simplest answer to the specific question, avoiding the use of ring homomorphisms and residue classes. (Note: You should learn about ring homomorphisms and residue classes if you want to get anywhere in abstract algebra; you won't always be able to work as concretely as below.)
Fix a nonnegative integer $n$. We let $left[nright]$ denote the set $left{1,2,ldots,nright}$.
Lemma 1. Let $A = left(a_{i,j}right)_{i, j in left[nright]}$ and $B = left(b_{i,j}right)_{i, j in left[nright]}$ be two $ntimes n$-matrices of integers. Let $N$ be an integer. Assume that
begin{equation}
a_{i,j} equiv b_{i,j} mod N
label{darij.eq.l1.1}
tag{1}
end{equation}
for all $i, j in left[nright]$. Then, $det A equiv det B mod N$.
Proof of Lemma 1. The Leibniz formula for determinants yields $det A = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n a_{i, sigmaleft(iright)}$ and $det B = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}$ (where $S_n$ denotes the set of all permutations of $left[nright]$, and where $left(-1right)^{sigma}$ denotes the sign of a permutation $sigma$). Thus,
begin{align}
det A
& = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n underbrace{a_{i, sigmaleft(iright)}}_{substack{equiv b_{i, sigmaleft(iright)} mod N \ left(text{by eqref{darij.eq.l1.1}}right)}} \
& equiv sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}
= det B mod N
end{align}
(here, we tacitly used the fact that everything in our expressions is an integer, and that congruences modulo $N$ can be multiplied).
This proves Lemma 1. $blacksquare$
Corollary 2. Let $A$ be an $n times n$-matrix of integers such that all diagonal entries of $A$ are odd and all non-diagonal entries of $A$ are even. Then, $det A$ is odd.
Proof of Corollary 2. Write the matrix $A$ as $A = left(a_{i,j}right)_{i, j in left[nright]}$. Also, write the identity $ntimes n$-matrix $I_n$ as $I_n = left(b_{i,j}right)_{i, j in left[nright]}$. Then, it is easy to prove the congruence $a_{i,j} equiv b_{i,j} mod 2$ for all $i, j in left[nright]$. (Indeed, if $i = j$, then $a_{i,j}$ is a diagonal entry of $A$, whereas $b_{i,j}$ is a diagonal entry of $I_n$ and thus equals $1$; hence, this congruence says that all diagonal entries of $A$ are odd. This is true by assumption. On the other hand, if $i neq j$, then $a_{i,j}$ is a non-diagonal entry of $A$, whereas $b_{i,j}$ is a non-diagonal entry of $I_n$ and thus equals $0$; hence, this congruence says that all non-diagonal entries of $A$ are even. This is again true by assumption. Thus, the congruence holds in both cases $i = j$ and $i neq j$.)
Thus, Lemma 1 (applied to $N=2$ and $B=I_n$) yields $det A equiv detleft(I_nright) = 1 mod 2$. In other words, $det A$ is odd. $blacksquare$
Corollary 2 can be directly applied to your matrix $A$.
answered Dec 31 '18 at 22:33
darij grinbergdarij grinberg
10.4k33062
Here is perhaps the simplest answer to the specific question, avoiding the use of ring homomorphisms and residue classes. (Note: You should learn about ring homomorphisms and residue classes if you want to get anywhere in abstract algebra; you won't always be able to work as concretely as below.)
Fix a nonnegative integer $n$. We let $left[nright]$ denote the set $left{1,2,ldots,nright}$.
Lemma 1. Let $A = left(a_{i,j}right)_{i, j in left[nright]}$ and $B = left(b_{i,j}right)_{i, j in left[nright]}$ be two $ntimes n$-matrices of integers. Let $N$ be an integer. Assume that
begin{equation}
a_{i,j} equiv b_{i,j} mod N
label{darij.eq.l1.1}
tag{1}
end{equation}
for all $i, j in left[nright]$. Then, $det A equiv det B mod N$.
Proof of Lemma 1. The Leibniz formula for determinants yields $det A = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n a_{i, sigmaleft(iright)}$ and $det B = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}$ (where $S_n$ denotes the set of all permutations of $left[nright]$, and where $left(-1right)^{sigma}$ denotes the sign of a permutation $sigma$). Thus,
begin{align}
det A
& = sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n underbrace{a_{i, sigmaleft(iright)}}_{substack{equiv b_{i, sigmaleft(iright)} mod N \ left(text{by eqref{darij.eq.l1.1}}right)}} \
& equiv sumlimits_{sigma in S_n} left(-1right)^{sigma} prodlimits_{i=1}^n b_{i, sigmaleft(iright)}
= det B mod N
end{align}
(here, we tacitly used the fact that everything in our expressions is an integer, and that congruences modulo $N$ can be multiplied).
This proves Lemma 1. $blacksquare$
Corollary 2. Let $A$ be an $n times n$-matrix of integers such that all diagonal entries of $A$ are odd and all non-diagonal entries of $A$ are even. Then, $det A$ is odd.
Proof of Corollary 2. Write the matrix $A$ as $A = left(a_{i,j}right)_{i, j in left[nright]}$. Also, write the identity $ntimes n$-matrix $I_n$ as $I_n = left(b_{i,j}right)_{i, j in left[nright]}$. Then, it is easy to prove the congruence $a_{i,j} equiv b_{i,j} mod 2$ for all $i, j in left[nright]$. (Indeed, if $i = j$, then $a_{i,j}$ is a diagonal entry of $A$, whereas $b_{i,j}$ is a diagonal entry of $I_n$ and thus equals $1$; hence, this congruence says that all diagonal entries of $A$ are odd. This is true by assumption. On the other hand, if $i neq j$, then $a_{i,j}$ is a non-diagonal entry of $A$, whereas $b_{i,j}$ is a non-diagonal entry of $I_n$ and thus equals $0$; hence, this congruence says that all non-diagonal entries of $A$ are even. This is again true by assumption. Thus, the congruence holds in both cases $i = j$ and $i neq j$.)
Thus, Lemma 1 (applied to $N=2$ and $B=I_n$) yields $det A equiv detleft(I_nright) = 1 mod 2$. In other words, $det A$ is odd. $blacksquare$
Corollary 2 can be directly applied to your matrix $A$.
answered Dec 31 '18 at 22:33
darij grinbergdarij grinberg
10.4k33062
answered Dec 31 '18 at 22:33
darij grinbergdarij grinberg
10.4k33062
answered Dec 31 '18 at 22:33
darij grinbergdarij grinberg
10.4k33062
answered Dec 31 '18 at 22:33
darij grinbergdarij grinberg
10.4k33062
10.4k33062
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3057908%2fusing-bara-a-modulo-2-to-prove-that-a-is-invertible%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
"$det(A)=det(bar{A}) (text{mod} 2)$" is nonsense. What is meant is: The residue class of $detleft(Aright)$ modulo $2$ is $detleft(overline{A}right) = 1$.
– darij grinberg
Dec 31 '18 at 18:27
I dont understand how this is so hard to understand!
– Permian
Dec 31 '18 at 18:37
Ideally I would like as simple an answer as possible
– Permian
Dec 31 '18 at 21:51