The minimum rank of a matrix with a given pattern of zeros
For real matrices $A=(a_{ij})$ and $B=(b_{ij})$ of the same size, I write $Aprec B$ if $a_{ij}=0$ whenever $b_{ij}=0$.
If
$$ B = begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ 1 & 0 & 1 end{pmatrix}^{otimes10}, $$
then the matrix
$$ A = begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ -1 & 0 & 1 end{pmatrix}^{otimes10} $$
satisfies $mathrm{rk}(A)<mathrm{rk}(B)$ and $Iprec Aprec B$ (where $I$ is the identity matrix of order $3^{10}$) . Does there exist a square matrix $C$ of order $3^{10}$ such that $mathrm{rk}(C)<mathrm{rk}(A)$ and $Iprec Cprec A$?
linear-algebra matrices
asked Dec 22 '18 at 11:01
Seva
12.4k137102
add a comment |
For real matrices $A=(a_{ij})$ and $B=(b_{ij})$ of the same size, I write $Aprec B$ if $a_{ij}=0$ whenever $b_{ij}=0$.
If
$$ B = begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ 1 & 0 & 1 end{pmatrix}^{otimes10}, $$
then the matrix
$$ A = begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ -1 & 0 & 1 end{pmatrix}^{otimes10} $$
satisfies $mathrm{rk}(A)<mathrm{rk}(B)$ and $Iprec Aprec B$ (where $I$ is the identity matrix of order $3^{10}$) . Does there exist a square matrix $C$ of order $3^{10}$ such that $mathrm{rk}(C)<mathrm{rk}(A)$ and $Iprec Cprec A$?
linear-algebra matrices
asked Dec 22 '18 at 11:01
Seva
12.4k137102
add a comment |
For real matrices $A=(a_{ij})$ and $B=(b_{ij})$ of the same size, I write $Aprec B$ if $a_{ij}=0$ whenever $b_{ij}=0$.
If
$$ B = begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ 1 & 0 & 1 end{pmatrix}^{otimes10}, $$
then the matrix
$$ A = begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ -1 & 0 & 1 end{pmatrix}^{otimes10} $$
satisfies $mathrm{rk}(A)<mathrm{rk}(B)$ and $Iprec Aprec B$ (where $I$ is the identity matrix of order $3^{10}$) . Does there exist a square matrix $C$ of order $3^{10}$ such that $mathrm{rk}(C)<mathrm{rk}(A)$ and $Iprec Cprec A$?
linear-algebra matrices
asked Dec 22 '18 at 11:01
Seva
12.4k137102
For real matrices $A=(a_{ij})$ and $B=(b_{ij})$ of the same size, I write $Aprec B$ if $a_{ij}=0$ whenever $b_{ij}=0$.
If
$$ B = begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ 1 & 0 & 1 end{pmatrix}^{otimes10}, $$
then the matrix
$$ A = begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ -1 & 0 & 1 end{pmatrix}^{otimes10} $$
satisfies $mathrm{rk}(A)<mathrm{rk}(B)$ and $Iprec Aprec B$ (where $I$ is the identity matrix of order $3^{10}$) . Does there exist a square matrix $C$ of order $3^{10}$ such that $mathrm{rk}(C)<mathrm{rk}(A)$ and $Iprec Cprec A$?
linear-algebra matrices
linear-algebra matrices
asked Dec 22 '18 at 11:01
Seva
12.4k137102
asked Dec 22 '18 at 11:01
Seva
12.4k137102
asked Dec 22 '18 at 11:01
Seva
12.4k137102
asked Dec 22 '18 at 11:01
Seva
12.4k137102
asked Dec 22 '18 at 11:01
Seva
12.4k137102
12.4k137102
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
As Misha Muzychuck has observed, the answer is "no": since
$$ begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ -1 & 0 & 1 end{pmatrix} $$ contains a non-degenerate upper-triangular submatrix of size $2$, the matrix $A$ contains a non-degenerate upper-triangular submatrix of size $2^{10}$, whence $mathrm{rk}(C)ge 2^{10}=mathrm{rk}(A)$ for any matrix $C$ with $Iprec Cprec A$.
answered Dec 22 '18 at 12:02
Seva
12.4k137102
2
just curious: since ${rm rk}(A)=2^{10}$, it implies that $A$ does not contain a non-degenerate upper-triangular-after-permutation submatrix of size greater than $2^{10}$. Is it obvious a priori without linear algebra (on the size of directed graphs)?
– Fedor Petrov
Dec 22 '18 at 12:21
@FedorPetrov: In fact, I cannot even prove without using linear algebra / polynomials that $(A-A)cap{0,1}^nne{0}$ for any set $Asubsetmathbb F_3^n$ with $|A|>2^n$ (can you?)
– Seva
Dec 23 '18 at 19:35
1
I can not. But recently it was slightly improved arxiv.org/abs/1812.05989 (again with linear algebra)
– Fedor Petrov
Dec 23 '18 at 20:37
@FedorPetrov: Interestingly, there is a huge set $Asubsetmathbb F_3^n$ (of size $|A|ge 3^{n-1}$) and a very large subset $D_0subset{0,1}$ (of size $|D_0|gtrsim frac13cdot 2^n$) such that $A-A$ is disjoint from $D_0$.
– Seva
Dec 25 '18 at 18:06
probably even $frac 23 cdot 2^n$? If $A$ lies in some hyperplane.
– Fedor Petrov
Dec 26 '18 at 7:27
|
show 1 more 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: "504"
};
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%2fmathoverflow.net%2fquestions%2f319275%2fthe-minimum-rank-of-a-matrix-with-a-given-pattern-of-zeros%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
As Misha Muzychuck has observed, the answer is "no": since
$$ begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ -1 & 0 & 1 end{pmatrix} $$ contains a non-degenerate upper-triangular submatrix of size $2$, the matrix $A$ contains a non-degenerate upper-triangular submatrix of size $2^{10}$, whence $mathrm{rk}(C)ge 2^{10}=mathrm{rk}(A)$ for any matrix $C$ with $Iprec Cprec A$.
answered Dec 22 '18 at 12:02
Seva
12.4k137102
2
just curious: since ${rm rk}(A)=2^{10}$, it implies that $A$ does not contain a non-degenerate upper-triangular-after-permutation submatrix of size greater than $2^{10}$. Is it obvious a priori without linear algebra (on the size of directed graphs)?
– Fedor Petrov
Dec 22 '18 at 12:21
@FedorPetrov: In fact, I cannot even prove without using linear algebra / polynomials that $(A-A)cap{0,1}^nne{0}$ for any set $Asubsetmathbb F_3^n$ with $|A|>2^n$ (can you?)
– Seva
Dec 23 '18 at 19:35
1
I can not. But recently it was slightly improved arxiv.org/abs/1812.05989 (again with linear algebra)
– Fedor Petrov
Dec 23 '18 at 20:37
@FedorPetrov: Interestingly, there is a huge set $Asubsetmathbb F_3^n$ (of size $|A|ge 3^{n-1}$) and a very large subset $D_0subset{0,1}$ (of size $|D_0|gtrsim frac13cdot 2^n$) such that $A-A$ is disjoint from $D_0$.
– Seva
Dec 25 '18 at 18:06
probably even $frac 23 cdot 2^n$? If $A$ lies in some hyperplane.
– Fedor Petrov
Dec 26 '18 at 7:27
|
show 1 more comment
As Misha Muzychuck has observed, the answer is "no": since
$$ begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ -1 & 0 & 1 end{pmatrix} $$ contains a non-degenerate upper-triangular submatrix of size $2$, the matrix $A$ contains a non-degenerate upper-triangular submatrix of size $2^{10}$, whence $mathrm{rk}(C)ge 2^{10}=mathrm{rk}(A)$ for any matrix $C$ with $Iprec Cprec A$.
answered Dec 22 '18 at 12:02
Seva
12.4k137102
2
just curious: since ${rm rk}(A)=2^{10}$, it implies that $A$ does not contain a non-degenerate upper-triangular-after-permutation submatrix of size greater than $2^{10}$. Is it obvious a priori without linear algebra (on the size of directed graphs)?
– Fedor Petrov
Dec 22 '18 at 12:21
@FedorPetrov: In fact, I cannot even prove without using linear algebra / polynomials that $(A-A)cap{0,1}^nne{0}$ for any set $Asubsetmathbb F_3^n$ with $|A|>2^n$ (can you?)
– Seva
Dec 23 '18 at 19:35
1
I can not. But recently it was slightly improved arxiv.org/abs/1812.05989 (again with linear algebra)
– Fedor Petrov
Dec 23 '18 at 20:37
@FedorPetrov: Interestingly, there is a huge set $Asubsetmathbb F_3^n$ (of size $|A|ge 3^{n-1}$) and a very large subset $D_0subset{0,1}$ (of size $|D_0|gtrsim frac13cdot 2^n$) such that $A-A$ is disjoint from $D_0$.
– Seva
Dec 25 '18 at 18:06
probably even $frac 23 cdot 2^n$? If $A$ lies in some hyperplane.
– Fedor Petrov
Dec 26 '18 at 7:27
|
show 1 more comment
As Misha Muzychuck has observed, the answer is "no": since
$$ begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ -1 & 0 & 1 end{pmatrix} $$ contains a non-degenerate upper-triangular submatrix of size $2$, the matrix $A$ contains a non-degenerate upper-triangular submatrix of size $2^{10}$, whence $mathrm{rk}(C)ge 2^{10}=mathrm{rk}(A)$ for any matrix $C$ with $Iprec Cprec A$.
answered Dec 22 '18 at 12:02
Seva
12.4k137102
As Misha Muzychuck has observed, the answer is "no": since
$$ begin{pmatrix} 1 & 1 & 0 \ 0 & 1 & 1 \ -1 & 0 & 1 end{pmatrix} $$ contains a non-degenerate upper-triangular submatrix of size $2$, the matrix $A$ contains a non-degenerate upper-triangular submatrix of size $2^{10}$, whence $mathrm{rk}(C)ge 2^{10}=mathrm{rk}(A)$ for any matrix $C$ with $Iprec Cprec A$.
answered Dec 22 '18 at 12:02
Seva
12.4k137102
answered Dec 22 '18 at 12:02
Seva
12.4k137102
answered Dec 22 '18 at 12:02
Seva
12.4k137102
answered Dec 22 '18 at 12:02
Seva
12.4k137102
12.4k137102
2
just curious: since ${rm rk}(A)=2^{10}$, it implies that $A$ does not contain a non-degenerate upper-triangular-after-permutation submatrix of size greater than $2^{10}$. Is it obvious a priori without linear algebra (on the size of directed graphs)?
– Fedor Petrov
Dec 22 '18 at 12:21
@FedorPetrov: In fact, I cannot even prove without using linear algebra / polynomials that $(A-A)cap{0,1}^nne{0}$ for any set $Asubsetmathbb F_3^n$ with $|A|>2^n$ (can you?)
– Seva
Dec 23 '18 at 19:35
1
I can not. But recently it was slightly improved arxiv.org/abs/1812.05989 (again with linear algebra)
– Fedor Petrov
Dec 23 '18 at 20:37
@FedorPetrov: Interestingly, there is a huge set $Asubsetmathbb F_3^n$ (of size $|A|ge 3^{n-1}$) and a very large subset $D_0subset{0,1}$ (of size $|D_0|gtrsim frac13cdot 2^n$) such that $A-A$ is disjoint from $D_0$.
– Seva
Dec 25 '18 at 18:06
probably even $frac 23 cdot 2^n$? If $A$ lies in some hyperplane.
– Fedor Petrov
Dec 26 '18 at 7:27
|
show 1 more comment
2
just curious: since ${rm rk}(A)=2^{10}$, it implies that $A$ does not contain a non-degenerate upper-triangular-after-permutation submatrix of size greater than $2^{10}$. Is it obvious a priori without linear algebra (on the size of directed graphs)?
– Fedor Petrov
Dec 22 '18 at 12:21
@FedorPetrov: In fact, I cannot even prove without using linear algebra / polynomials that $(A-A)cap{0,1}^nne{0}$ for any set $Asubsetmathbb F_3^n$ with $|A|>2^n$ (can you?)
– Seva
Dec 23 '18 at 19:35
1
I can not. But recently it was slightly improved arxiv.org/abs/1812.05989 (again with linear algebra)
– Fedor Petrov
Dec 23 '18 at 20:37
@FedorPetrov: Interestingly, there is a huge set $Asubsetmathbb F_3^n$ (of size $|A|ge 3^{n-1}$) and a very large subset $D_0subset{0,1}$ (of size $|D_0|gtrsim frac13cdot 2^n$) such that $A-A$ is disjoint from $D_0$.
– Seva
Dec 25 '18 at 18:06
probably even $frac 23 cdot 2^n$? If $A$ lies in some hyperplane.
– Fedor Petrov
Dec 26 '18 at 7:27
2
2
just curious: since ${rm rk}(A)=2^{10}$, it implies that $A$ does not contain a non-degenerate upper-triangular-after-permutation submatrix of size greater than $2^{10}$. Is it obvious a priori without linear algebra (on the size of directed graphs)?
– Fedor Petrov
Dec 22 '18 at 12:21
just curious: since ${rm rk}(A)=2^{10}$, it implies that $A$ does not contain a non-degenerate upper-triangular-after-permutation submatrix of size greater than $2^{10}$. Is it obvious a priori without linear algebra (on the size of directed graphs)?
– Fedor Petrov
Dec 22 '18 at 12:21
@FedorPetrov: In fact, I cannot even prove without using linear algebra / polynomials that $(A-A)cap{0,1}^nne{0}$ for any set $Asubsetmathbb F_3^n$ with $|A|>2^n$ (can you?)
– Seva
Dec 23 '18 at 19:35
@FedorPetrov: In fact, I cannot even prove without using linear algebra / polynomials that $(A-A)cap{0,1}^nne{0}$ for any set $Asubsetmathbb F_3^n$ with $|A|>2^n$ (can you?)
– Seva
Dec 23 '18 at 19:35
1
1
I can not. But recently it was slightly improved arxiv.org/abs/1812.05989 (again with linear algebra)
– Fedor Petrov
Dec 23 '18 at 20:37
I can not. But recently it was slightly improved arxiv.org/abs/1812.05989 (again with linear algebra)
– Fedor Petrov
Dec 23 '18 at 20:37
@FedorPetrov: Interestingly, there is a huge set $Asubsetmathbb F_3^n$ (of size $|A|ge 3^{n-1}$) and a very large subset $D_0subset{0,1}$ (of size $|D_0|gtrsim frac13cdot 2^n$) such that $A-A$ is disjoint from $D_0$.
– Seva
Dec 25 '18 at 18:06
@FedorPetrov: Interestingly, there is a huge set $Asubsetmathbb F_3^n$ (of size $|A|ge 3^{n-1}$) and a very large subset $D_0subset{0,1}$ (of size $|D_0|gtrsim frac13cdot 2^n$) such that $A-A$ is disjoint from $D_0$.
– Seva
Dec 25 '18 at 18:06
probably even $frac 23 cdot 2^n$? If $A$ lies in some hyperplane.
– Fedor Petrov
Dec 26 '18 at 7:27
probably even $frac 23 cdot 2^n$? If $A$ lies in some hyperplane.
– Fedor Petrov
Dec 26 '18 at 7:27
|
show 1 more comment
Thanks for contributing an answer to MathOverflow!
- 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fmathoverflow.net%2fquestions%2f319275%2fthe-minimum-rank-of-a-matrix-with-a-given-pattern-of-zeros%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
