Mixing
If matrix $A$ is totally unimodular, then matrix $beginbmatrix A &pm Aendbmatrix$ is also totally unimodular
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Given a totally unimodular matrix $A in-1,0,1^mtimes n$, show that the matrix $$beginbmatrix A &pm Aendbmatrix$$ is also totally unimodular.
I want to prove that exchanging any two columns in $A$ will still be unimodular at first but it seems that the idea is wrong. Thanks in advanceï¼Â
linear-algebra matrices linear-programming total-unimodularity unimodular-matrices
edited Jul 27 at 6:02
Rodrigo de Azevedo
12.5k41751
asked Jul 27 at 5:40
wst
114
add a comment |Â
up vote
0
down vote
favorite
Given a totally unimodular matrix $A in-1,0,1^mtimes n$, show that the matrix $$beginbmatrix A &pm Aendbmatrix$$ is also totally unimodular.
I want to prove that exchanging any two columns in $A$ will still be unimodular at first but it seems that the idea is wrong. Thanks in advanceï¼Â
linear-algebra matrices linear-programming total-unimodularity unimodular-matrices
edited Jul 27 at 6:02
Rodrigo de Azevedo
12.5k41751
asked Jul 27 at 5:40
wst
114
Sorry at last this is not a hard problem, it's because I was not clearly understood the definition of square submatrix.
– wst
Jul 27 at 7:09
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Given a totally unimodular matrix $A in-1,0,1^mtimes n$, show that the matrix $$beginbmatrix A &pm Aendbmatrix$$ is also totally unimodular.
I want to prove that exchanging any two columns in $A$ will still be unimodular at first but it seems that the idea is wrong. Thanks in advanceï¼Â
linear-algebra matrices linear-programming total-unimodularity unimodular-matrices
edited Jul 27 at 6:02
Rodrigo de Azevedo
12.5k41751
asked Jul 27 at 5:40
wst
114
Given a totally unimodular matrix $A in-1,0,1^mtimes n$, show that the matrix $$beginbmatrix A &pm Aendbmatrix$$ is also totally unimodular.
I want to prove that exchanging any two columns in $A$ will still be unimodular at first but it seems that the idea is wrong. Thanks in advanceï¼Â
linear-algebra matrices linear-programming total-unimodularity unimodular-matrices
edited Jul 27 at 6:02
Rodrigo de Azevedo
12.5k41751
asked Jul 27 at 5:40
wst
114
edited Jul 27 at 6:02
Rodrigo de Azevedo
12.5k41751
edited Jul 27 at 6:02
Rodrigo de Azevedo
12.5k41751
edited Jul 27 at 6:02
Rodrigo de Azevedo
12.5k41751
12.5k41751
asked Jul 27 at 5:40
wst
114
asked Jul 27 at 5:40
wst
114
asked Jul 27 at 5:40
wst
114
114
Sorry at last this is not a hard problem, it's because I was not clearly understood the definition of square submatrix.
– wst
Jul 27 at 7:09
add a comment |Â
Sorry at last this is not a hard problem, it's because I was not clearly understood the definition of square submatrix.
– wst
Jul 27 at 7:09
Sorry at last this is not a hard problem, it's because I was not clearly understood the definition of square submatrix.
– wst
Jul 27 at 7:09
Sorry at last this is not a hard problem, it's because I was not clearly understood the definition of square submatrix.
– wst
Jul 27 at 7:09
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
The goal is to show that if a square submatrix of $[A,pm A]$ is nonsingular then it has determinant $pm 1$. Observe that any nonsingular square submatrix of $[A,pm A]$ is (up to permutation and sign of the columns) a nonsingular square submatrix of $A$ (justified later). Hence since permutation changes determinants by the sign of the permutation, which is $pm 1$, and changing the sign of a columns also multiplies the determinant by $-1$ for each such column, we observe that this implies that the determinant of every nonsingular square submatrix of $[A,pm A]$ is $pm 1$.
Now to justify the claim. Well, if we choose a square submatrix of $[A,pm A]$, we are choosing a subset of the rows and columns of $[A,pm A]$. Let's label the columns of $[A,pm A]$ as $C_1,ldots,C_n,C_n+1,C_2n$.
By definition $C_i=pm C_i+n$ for $1le ile n$, so if the subset of the columns that we choose contains index $i$ and $i+n$ for some $1le ile n$, the resulting matrix must have determinant 0 because $C_i$ and $C_i+n$ will be linearly dependent no matter what subset of the rows we choose. Thus there is a map identifying the subset of the columns of $[A,pm A]$ with a subset of the columns of $A$ given by
$$ imapsto begincases i & textrmif $1le i le n$ \ i-n & textrmotherwise.endcases. $$
answered Jul 27 at 6:01
jgon
8,54611335
Thank you very much...
– wst
Jul 27 at 7:08
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
The goal is to show that if a square submatrix of $[A,pm A]$ is nonsingular then it has determinant $pm 1$. Observe that any nonsingular square submatrix of $[A,pm A]$ is (up to permutation and sign of the columns) a nonsingular square submatrix of $A$ (justified later). Hence since permutation changes determinants by the sign of the permutation, which is $pm 1$, and changing the sign of a columns also multiplies the determinant by $-1$ for each such column, we observe that this implies that the determinant of every nonsingular square submatrix of $[A,pm A]$ is $pm 1$.
Now to justify the claim. Well, if we choose a square submatrix of $[A,pm A]$, we are choosing a subset of the rows and columns of $[A,pm A]$. Let's label the columns of $[A,pm A]$ as $C_1,ldots,C_n,C_n+1,C_2n$.
By definition $C_i=pm C_i+n$ for $1le ile n$, so if the subset of the columns that we choose contains index $i$ and $i+n$ for some $1le ile n$, the resulting matrix must have determinant 0 because $C_i$ and $C_i+n$ will be linearly dependent no matter what subset of the rows we choose. Thus there is a map identifying the subset of the columns of $[A,pm A]$ with a subset of the columns of $A$ given by
$$ imapsto begincases i & textrmif $1le i le n$ \ i-n & textrmotherwise.endcases. $$
answered Jul 27 at 6:01
jgon
8,54611335
Thank you very much...
– wst
Jul 27 at 7:08
add a comment |Â
up vote
1
down vote
accepted
The goal is to show that if a square submatrix of $[A,pm A]$ is nonsingular then it has determinant $pm 1$. Observe that any nonsingular square submatrix of $[A,pm A]$ is (up to permutation and sign of the columns) a nonsingular square submatrix of $A$ (justified later). Hence since permutation changes determinants by the sign of the permutation, which is $pm 1$, and changing the sign of a columns also multiplies the determinant by $-1$ for each such column, we observe that this implies that the determinant of every nonsingular square submatrix of $[A,pm A]$ is $pm 1$.
Now to justify the claim. Well, if we choose a square submatrix of $[A,pm A]$, we are choosing a subset of the rows and columns of $[A,pm A]$. Let's label the columns of $[A,pm A]$ as $C_1,ldots,C_n,C_n+1,C_2n$.
By definition $C_i=pm C_i+n$ for $1le ile n$, so if the subset of the columns that we choose contains index $i$ and $i+n$ for some $1le ile n$, the resulting matrix must have determinant 0 because $C_i$ and $C_i+n$ will be linearly dependent no matter what subset of the rows we choose. Thus there is a map identifying the subset of the columns of $[A,pm A]$ with a subset of the columns of $A$ given by
$$ imapsto begincases i & textrmif $1le i le n$ \ i-n & textrmotherwise.endcases. $$
answered Jul 27 at 6:01
jgon
8,54611335
Thank you very much...
– wst
Jul 27 at 7:08
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
The goal is to show that if a square submatrix of $[A,pm A]$ is nonsingular then it has determinant $pm 1$. Observe that any nonsingular square submatrix of $[A,pm A]$ is (up to permutation and sign of the columns) a nonsingular square submatrix of $A$ (justified later). Hence since permutation changes determinants by the sign of the permutation, which is $pm 1$, and changing the sign of a columns also multiplies the determinant by $-1$ for each such column, we observe that this implies that the determinant of every nonsingular square submatrix of $[A,pm A]$ is $pm 1$.
Now to justify the claim. Well, if we choose a square submatrix of $[A,pm A]$, we are choosing a subset of the rows and columns of $[A,pm A]$. Let's label the columns of $[A,pm A]$ as $C_1,ldots,C_n,C_n+1,C_2n$.
By definition $C_i=pm C_i+n$ for $1le ile n$, so if the subset of the columns that we choose contains index $i$ and $i+n$ for some $1le ile n$, the resulting matrix must have determinant 0 because $C_i$ and $C_i+n$ will be linearly dependent no matter what subset of the rows we choose. Thus there is a map identifying the subset of the columns of $[A,pm A]$ with a subset of the columns of $A$ given by
$$ imapsto begincases i & textrmif $1le i le n$ \ i-n & textrmotherwise.endcases. $$
answered Jul 27 at 6:01
jgon
8,54611335
The goal is to show that if a square submatrix of $[A,pm A]$ is nonsingular then it has determinant $pm 1$. Observe that any nonsingular square submatrix of $[A,pm A]$ is (up to permutation and sign of the columns) a nonsingular square submatrix of $A$ (justified later). Hence since permutation changes determinants by the sign of the permutation, which is $pm 1$, and changing the sign of a columns also multiplies the determinant by $-1$ for each such column, we observe that this implies that the determinant of every nonsingular square submatrix of $[A,pm A]$ is $pm 1$.
Now to justify the claim. Well, if we choose a square submatrix of $[A,pm A]$, we are choosing a subset of the rows and columns of $[A,pm A]$. Let's label the columns of $[A,pm A]$ as $C_1,ldots,C_n,C_n+1,C_2n$.
By definition $C_i=pm C_i+n$ for $1le ile n$, so if the subset of the columns that we choose contains index $i$ and $i+n$ for some $1le ile n$, the resulting matrix must have determinant 0 because $C_i$ and $C_i+n$ will be linearly dependent no matter what subset of the rows we choose. Thus there is a map identifying the subset of the columns of $[A,pm A]$ with a subset of the columns of $A$ given by
$$ imapsto begincases i & textrmif $1le i le n$ \ i-n & textrmotherwise.endcases. $$
answered Jul 27 at 6:01
jgon
8,54611335
answered Jul 27 at 6:01
jgon
8,54611335
answered Jul 27 at 6:01
jgon
8,54611335
answered Jul 27 at 6:01
jgon
8,54611335
8,54611335
Thank you very much...
– wst
Jul 27 at 7:08
add a comment |Â
Thank you very much...
– wst
Jul 27 at 7:08
Thank you very much...
– wst
Jul 27 at 7:08
Thank you very much...
– wst
Jul 27 at 7:08
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2864087%2fif-matrix-a-is-totally-unimodular-then-matrix-beginbmatrix-a-pm-a-endb%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Sorry at last this is not a hard problem, it's because I was not clearly understood the definition of square submatrix.
– wst
Jul 27 at 7:09