2
$\begingroup$

I have some (rather exotic) subspace $L<R^n$, and I want to show that every non-zero vector in $\{0,1\}^n$ has a relatively small projection onto $L$. What general results and tools can be helpful? Anything from geometry of numbers?

Any suggestions appreciated!

Upon looking at the responses, some explanations may be in order. Let's say that a subspace $L<R^n$ is oblique if for any vector $z\in\{0,1\}^n$, the projection of $z$ onto $L$ is of length at most $\|z\|/\log\log n$ (say). What properties of a subspace can ensure that it is oblique? Can any general "obliqueness criteria" be given?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Please state a reasonable question and give background. As is, I vote to close. $\endgroup$
    – Bill Johnson
    Commented Apr 4, 2011 at 20:39
  • 2
    $\begingroup$ I second Bill's vote. I don't care much about the background but a legitimate question should be far more precise than this. As of now, I do not even understand what "relatively small" might mean here. Indeed, no vector is longer than $\sqrt n$ and, unless your subspace is more or less aligned with some coordinate plane of small dimension, there is little chance to get much less for the maximal projection. $\endgroup$
    – fedja
    Commented Apr 5, 2011 at 3:14
  • $\begingroup$ @Bill: I believe, it is reasonable to request background for extremely specialized and artificially looking questions. This is certainly not the case with a general question like this. The question is motivated by my attempt to construct a graph with some particular property, but I am certainly not in a position to describe here all the work which led me to this question. $\endgroup$
    – Seva
    Commented Apr 5, 2011 at 6:50
  • $\begingroup$ @fedja: I explained above what I mean by "relatively small". As to you last remark: if the subspace is aligned with some coordinate plane, then it most certainly does not have the property in question. Loosely speaking, what I need is a criterion to show that a subspace is not aligned with the coordinate planes! $\endgroup$
    – Seva
    Commented Apr 5, 2011 at 6:53
  • $\begingroup$ I suggest re-editing or posting a new question with a description of the invariant subspace L and the clarification that you want the ratio. $\endgroup$
    – Aaron Meyerowitz
    Commented Apr 5, 2011 at 13:12

2 Answers 2

Reset to default
1
$\begingroup$

It would help to know what $L$ is.

update This answer was for the question of how short the longest projection could be if $L$ is allowed to vary. There have since been some clarifications.

Here is an upper bound which I think I can prove to be the minimum among all the $d$ dimensional spaces of $\mathbb{R}^n$ (with $n>d$ of course)

Let $L$ be the subspace of $\mathbb{R}^n$ consisting of vectors whose first $d+1$ coordinates sum to $0$ and whose remaining coordinates are $0$. Project the vectors of $\lbrace0,1\rbrace^n $ onto $L.$ The length of the longest projection is $$\begin{cases} \sqrt{\frac{d+1}{4}}, & \mbox{if }d=2k+1 \\ \\ \sqrt{\frac{d+1-\frac{1}{d+1}}{4}}, & \mbox{if }d=2k. \end{cases}$$

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks for an attempt to answer in essence - but I am afraid, I don't understood much here. For $d=1$ you seem to claim that the longest projection of a vector from $\{0,1\}^n$ onto your subspace is $0$, do you? Anyway, I am speaking about some particular subspace, and I need the length of the projection normalized by dividing by the length of the vector itself. $\endgroup$
    – Seva
    Commented Apr 5, 2011 at 7:02
  • $\begingroup$ Concerning "what $L$ actually is": is is an invariant subspace of a (high) tensor power of the "Fibonacci matrix" $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. I am not asking, however, to look at my particular problem; rather, I am to trying to figure out what are possible approaches and useful tools. $\endgroup$
    – Seva
    Commented Apr 5, 2011 at 7:04
  • $\begingroup$ OK, thanks, I think I fixed it. For $d=1$ the subspace spanned by $[1,-1,0,0,0,\cdots]$ sends some things to the zero vector and others to $[1/2,-1/2,0,0,0,\cdots]$. For $d=2$ some things go to $[2/3,-1/3,-1/3,0,0,0,\cdots]$. For $d=3$ some things go to $[1/2,1/2,-1/2,-1/2,0,0,\cdots]$. $\endgroup$
    – Aaron Meyerowitz
    Commented Apr 5, 2011 at 8:31
  • $\begingroup$ I see your point - but my question is not about the subspaces that you consider! I don't want all projections to be (relatively) small for any vector $z\in\{0,1\}^n$ and any subspace $L$ - I have some particular subspace $L$ in mind, and I wonder what properties of this my subspace can guarantee that it is "not aligned with the vectors from $\{0,1\}^n$". $\endgroup$
    – Seva
    Commented Apr 5, 2011 at 9:03
  • 1
    $\begingroup$ I am afraid there is still some misunderstanding here. Let's say that a subspace $L<R^n$ is good if for any $z\in\{0,1\}^n$, the projection of $z$ onto $L$ has length at most $\|z\|/\log\log n$. Good subspaces do exist: say, the one-dimensional subspace spanned by the vector $(1,1/\sqrt2,...,1/\sqrt n)$ is good. What I seek is a sufficiently general and versatile criterion for a subspace to be good. $\endgroup$
    – Seva
    Commented Apr 5, 2011 at 14:10
0
$\begingroup$

Look up Lindenstrauss-Johnson.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Lindenstrauss-Johnson says that there are subspaces which make the distance between the projections "close" to the distance between the original points. Here the desire is to have the projections be small so ideally one might want the projection to shrink distances as far as possible. $\endgroup$
    – Aaron Meyerowitz
    Commented Apr 4, 2011 at 23:16
  • 5
    $\begingroup$ It is usually called the Johnson-Lindenstrauss Lemma. :) $\endgroup$
    – Bill Johnson
    Commented Apr 5, 2011 at 7:08
  • $\begingroup$ True, my apologies, although it has long transcended lemma-hood. $\endgroup$
    – Igor Rivin
    Commented Apr 5, 2011 at 13:06
  • $\begingroup$ Not that I could see exactly how JL can help... $\endgroup$
    – Seva
    Commented Apr 5, 2011 at 13:29

Not the answer you're looking for? Browse other questions tagged .