Binary matrix with fixed inner product.
$begingroup$
Suppose that $m, n$ are two positive integers such that $m<<n$. Let $a, b, c$ be the three positive integers such that $aleq b < c$. Consider a binary matrix $Ain {0,1}^{mtimes n}$, such that for any two differnt columns $u$ and $v$ of matrix $A$, it is the case that,
$$aleqlangle u ,v rangle leq b,$$
and every column should contain at least $c$ numbers of $1's$.
Is it possible to construct such a matrix $A$ given the parameters $m,n, a,b,c$?
linear-algebra field-theory extension-field coding-theory finite-geometry
$endgroup$
add a comment |
$begingroup$
Suppose that $m, n$ are two positive integers such that $m<<n$. Let $a, b, c$ be the three positive integers such that $aleq b < c$. Consider a binary matrix $Ain {0,1}^{mtimes n}$, such that for any two differnt columns $u$ and $v$ of matrix $A$, it is the case that,
$$aleqlangle u ,v rangle leq b,$$
and every column should contain at least $c$ numbers of $1's$.
Is it possible to construct such a matrix $A$ given the parameters $m,n, a,b,c$?
linear-algebra field-theory extension-field coding-theory finite-geometry
$endgroup$
$begingroup$
The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
$endgroup$
– Berci
Jan 24 at 10:19
1
$begingroup$
This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
$endgroup$
– Eric
Jan 24 at 10:41
$begingroup$
I edited the question for both of you.
$endgroup$
– Shashank Ranjan
Jan 24 at 11:31
add a comment |
$begingroup$
Suppose that $m, n$ are two positive integers such that $m<<n$. Let $a, b, c$ be the three positive integers such that $aleq b < c$. Consider a binary matrix $Ain {0,1}^{mtimes n}$, such that for any two differnt columns $u$ and $v$ of matrix $A$, it is the case that,
$$aleqlangle u ,v rangle leq b,$$
and every column should contain at least $c$ numbers of $1's$.
Is it possible to construct such a matrix $A$ given the parameters $m,n, a,b,c$?
linear-algebra field-theory extension-field coding-theory finite-geometry
$endgroup$
Suppose that $m, n$ are two positive integers such that $m<<n$. Let $a, b, c$ be the three positive integers such that $aleq b < c$. Consider a binary matrix $Ain {0,1}^{mtimes n}$, such that for any two differnt columns $u$ and $v$ of matrix $A$, it is the case that,
$$aleqlangle u ,v rangle leq b,$$
and every column should contain at least $c$ numbers of $1's$.
Is it possible to construct such a matrix $A$ given the parameters $m,n, a,b,c$?
linear-algebra field-theory extension-field coding-theory finite-geometry
linear-algebra field-theory extension-field coding-theory finite-geometry
edited Jan 24 at 11:30
Shashank Ranjan
asked Jan 24 at 10:04
Shashank RanjanShashank Ranjan
84
84
$begingroup$
The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
$endgroup$
– Berci
Jan 24 at 10:19
1
$begingroup$
This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
$endgroup$
– Eric
Jan 24 at 10:41
$begingroup$
I edited the question for both of you.
$endgroup$
– Shashank Ranjan
Jan 24 at 11:31
add a comment |
$begingroup$
The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
$endgroup$
– Berci
Jan 24 at 10:19
1
$begingroup$
This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
$endgroup$
– Eric
Jan 24 at 10:41
$begingroup$
I edited the question for both of you.
$endgroup$
– Shashank Ranjan
Jan 24 at 11:31
$begingroup$
The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
$endgroup$
– Berci
Jan 24 at 10:19
$begingroup$
The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
$endgroup$
– Berci
Jan 24 at 10:19
1
1
$begingroup$
This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
$endgroup$
– Eric
Jan 24 at 10:41
$begingroup$
This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
$endgroup$
– Eric
Jan 24 at 10:41
$begingroup$
I edited the question for both of you.
$endgroup$
– Shashank Ranjan
Jan 24 at 11:31
$begingroup$
I edited the question for both of you.
$endgroup$
– Shashank Ranjan
Jan 24 at 11:31
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.
If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.
The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.
However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.
The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.
Much more than that requires more combinatorics that I can manage.
$endgroup$
add a comment |
$begingroup$
Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
${1,ldots,n}.$
So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$
A collection $cal A$ of subsets of
${1,ldots,n}$
is $L$-intersecting, if
for any two sets $A,B:$
$$Acap B in L$$
holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$
If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
$$
|cal A| leq binom{n}{s}
$$
otherwise
$$
|cal A| leq sum_{i=0}^s binom{n}{i}.
$$
For you $s=b-a+1.$
See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf
Edit: In general, good lower bounds are much harder to come by.
For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
$$
|cal A| geq (n/2k)^s,
$$
on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$
$endgroup$
$begingroup$
can you please provide lower bound on the cardinality of A ?
$endgroup$
– Shashank Ranjan
Jan 28 at 17:10
$begingroup$
Please see modified answer and upvote if the answer is satisfactory.
$endgroup$
– kodlu
Jan 28 at 22:27
$begingroup$
@kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
$endgroup$
– Shashank Ranjan
Jan 29 at 19:09
$begingroup$
It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
$endgroup$
– kodlu
Jan 29 at 20:48
$begingroup$
Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
$endgroup$
– Shashank Ranjan
Jan 29 at 22:30
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%2f3085688%2fbinary-matrix-with-fixed-inner-product%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.
If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.
The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.
However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.
The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.
Much more than that requires more combinatorics that I can manage.
$endgroup$
add a comment |
$begingroup$
This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.
If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.
The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.
However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.
The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.
Much more than that requires more combinatorics that I can manage.
$endgroup$
add a comment |
$begingroup$
This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.
If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.
The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.
However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.
The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.
Much more than that requires more combinatorics that I can manage.
$endgroup$
This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.
If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.
The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.
However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.
The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.
Much more than that requires more combinatorics that I can manage.
edited Jan 24 at 15:01
answered Jan 24 at 13:34
EricEric
3319
3319
add a comment |
add a comment |
$begingroup$
Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
${1,ldots,n}.$
So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$
A collection $cal A$ of subsets of
${1,ldots,n}$
is $L$-intersecting, if
for any two sets $A,B:$
$$Acap B in L$$
holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$
If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
$$
|cal A| leq binom{n}{s}
$$
otherwise
$$
|cal A| leq sum_{i=0}^s binom{n}{i}.
$$
For you $s=b-a+1.$
See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf
Edit: In general, good lower bounds are much harder to come by.
For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
$$
|cal A| geq (n/2k)^s,
$$
on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$
$endgroup$
$begingroup$
can you please provide lower bound on the cardinality of A ?
$endgroup$
– Shashank Ranjan
Jan 28 at 17:10
$begingroup$
Please see modified answer and upvote if the answer is satisfactory.
$endgroup$
– kodlu
Jan 28 at 22:27
$begingroup$
@kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
$endgroup$
– Shashank Ranjan
Jan 29 at 19:09
$begingroup$
It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
$endgroup$
– kodlu
Jan 29 at 20:48
$begingroup$
Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
$endgroup$
– Shashank Ranjan
Jan 29 at 22:30
add a comment |
$begingroup$
Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
${1,ldots,n}.$
So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$
A collection $cal A$ of subsets of
${1,ldots,n}$
is $L$-intersecting, if
for any two sets $A,B:$
$$Acap B in L$$
holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$
If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
$$
|cal A| leq binom{n}{s}
$$
otherwise
$$
|cal A| leq sum_{i=0}^s binom{n}{i}.
$$
For you $s=b-a+1.$
See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf
Edit: In general, good lower bounds are much harder to come by.
For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
$$
|cal A| geq (n/2k)^s,
$$
on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$
$endgroup$
$begingroup$
can you please provide lower bound on the cardinality of A ?
$endgroup$
– Shashank Ranjan
Jan 28 at 17:10
$begingroup$
Please see modified answer and upvote if the answer is satisfactory.
$endgroup$
– kodlu
Jan 28 at 22:27
$begingroup$
@kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
$endgroup$
– Shashank Ranjan
Jan 29 at 19:09
$begingroup$
It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
$endgroup$
– kodlu
Jan 29 at 20:48
$begingroup$
Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
$endgroup$
– Shashank Ranjan
Jan 29 at 22:30
add a comment |
$begingroup$
Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
${1,ldots,n}.$
So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$
A collection $cal A$ of subsets of
${1,ldots,n}$
is $L$-intersecting, if
for any two sets $A,B:$
$$Acap B in L$$
holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$
If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
$$
|cal A| leq binom{n}{s}
$$
otherwise
$$
|cal A| leq sum_{i=0}^s binom{n}{i}.
$$
For you $s=b-a+1.$
See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf
Edit: In general, good lower bounds are much harder to come by.
For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
$$
|cal A| geq (n/2k)^s,
$$
on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$
$endgroup$
Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
${1,ldots,n}.$
So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$
A collection $cal A$ of subsets of
${1,ldots,n}$
is $L$-intersecting, if
for any two sets $A,B:$
$$Acap B in L$$
holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$
If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
$$
|cal A| leq binom{n}{s}
$$
otherwise
$$
|cal A| leq sum_{i=0}^s binom{n}{i}.
$$
For you $s=b-a+1.$
See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf
Edit: In general, good lower bounds are much harder to come by.
For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
$$
|cal A| geq (n/2k)^s,
$$
on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$
edited Jan 28 at 22:26
answered Jan 26 at 21:48
kodlukodlu
3,390716
3,390716
$begingroup$
can you please provide lower bound on the cardinality of A ?
$endgroup$
– Shashank Ranjan
Jan 28 at 17:10
$begingroup$
Please see modified answer and upvote if the answer is satisfactory.
$endgroup$
– kodlu
Jan 28 at 22:27
$begingroup$
@kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
$endgroup$
– Shashank Ranjan
Jan 29 at 19:09
$begingroup$
It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
$endgroup$
– kodlu
Jan 29 at 20:48
$begingroup$
Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
$endgroup$
– Shashank Ranjan
Jan 29 at 22:30
add a comment |
$begingroup$
can you please provide lower bound on the cardinality of A ?
$endgroup$
– Shashank Ranjan
Jan 28 at 17:10
$begingroup$
Please see modified answer and upvote if the answer is satisfactory.
$endgroup$
– kodlu
Jan 28 at 22:27
$begingroup$
@kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
$endgroup$
– Shashank Ranjan
Jan 29 at 19:09
$begingroup$
It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
$endgroup$
– kodlu
Jan 29 at 20:48
$begingroup$
Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
$endgroup$
– Shashank Ranjan
Jan 29 at 22:30
$begingroup$
can you please provide lower bound on the cardinality of A ?
$endgroup$
– Shashank Ranjan
Jan 28 at 17:10
$begingroup$
can you please provide lower bound on the cardinality of A ?
$endgroup$
– Shashank Ranjan
Jan 28 at 17:10
$begingroup$
Please see modified answer and upvote if the answer is satisfactory.
$endgroup$
– kodlu
Jan 28 at 22:27
$begingroup$
Please see modified answer and upvote if the answer is satisfactory.
$endgroup$
– kodlu
Jan 28 at 22:27
$begingroup$
@kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
$endgroup$
– Shashank Ranjan
Jan 29 at 19:09
$begingroup$
@kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
$endgroup$
– Shashank Ranjan
Jan 29 at 19:09
$begingroup$
It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
$endgroup$
– kodlu
Jan 29 at 20:48
$begingroup$
It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
$endgroup$
– kodlu
Jan 29 at 20:48
$begingroup$
Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
$endgroup$
– Shashank Ranjan
Jan 29 at 22:30
$begingroup$
Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
$endgroup$
– Shashank Ranjan
Jan 29 at 22:30
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%2f3085688%2fbinary-matrix-with-fixed-inner-product%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
$begingroup$
The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
$endgroup$
– Berci
Jan 24 at 10:19
1
$begingroup$
This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
$endgroup$
– Eric
Jan 24 at 10:41
$begingroup$
I edited the question for both of you.
$endgroup$
– Shashank Ranjan
Jan 24 at 11:31