What Is the Maximum Number of Vectors with Non-Positive Inner Products in R^n?

  • Thread starter Thread starter tohauz
  • Start date Start date
  • Tags Tags
    Positive
tohauz
Messages
20
Reaction score
0
1. Suppose v_1, v_2, . . . v_k are non-zero vectors is R^n such that (v_i,v_j)<= 0 for all i,j. Determine, with proof, the maximal possible k for n = 3, and also for arbitrary n.
2. A is 2x2, A(1,1)=A(2,2)=x-1, A(1,2)=1, A(2,1)=0. Find invertible P,Q such that
P*A*Q is diagonal. I tried singular value decomposition, but calculations are getting nasty.
Please, give me hints for these problems. Thanks a lot
 
Physics news on Phys.org
tohauz said:
1. Suppose v_1, v_2, . . . v_k are non-zero vectors is R^n such that (v_i,v_j)<= 0 for all i,j. Determine, with proof, the maximal possible k for n = 3, and also for arbitrary n.
2. A is 2x2, A(1,1)=A(2,2)=x-1, A(1,2)=1, A(2,1)=0. Find invertible P,Q such that
P*A*Q is diagonal. I tried singular value decomposition, but calculations are getting nasty.
Please, give me hints for these problems. Thanks a lot

OK, I got the first one, hopefully somebody can help me 2nd.
1) Answer is 2n.
Use <u,v>=|u|*|v|*cosa, it is nonpositive if a>=90 degrees.
So in R^3 take i,j,k,-i,-j,-k. If you want to squeeze in other vector the angle
between that and 3 of those is less than 90.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top