[MATHS] Exercice TRIVIAL d'algèbre linéaire

On se place dans R^n, muni du produit scalaire usuel.
Considérez la famille M constituée :
-Des vecteurs de la base canoniques (e1 ... e1) .
-Des vecteurs opposés à ceux de la base canonique (-e1 ... -en).
-Des vecteurs dont toutes les coordonnées sont dans {-1,1}, qu'on nomme (c_1 ... c_s ). (Donc s=2^n).

Exercice :
On considère un vecteur u=/=0 de R^n dont le plus proche voisin (en termes d'angle), parmi les éléments de M, soit le plus éloigné possible. Quel est l'angle entre u et son plus proche voisin dans M ?

C'est trivial mais je ne sais pas résoudre çahttps://image.noelshack.com/fichiers/2016/49/1481122206-risipls.png
Un peu d'aide ?

EDIT : autrement dit on veut calculer min ( u =/= 0) max (d € M) [ u^T d / (||u|| ||d|| )].

http://sketchtoy.com/71046924
Ca c'est la solution dans R^2

Wesh la mif, alors là on va se poser dans R^n avec le produit scalaire qui va bien. T'as capté cette famille M de ouf avec les vecteurs de base canonique, leurs opposés et les (c_1 ... c_s) qui ont des coordonnées en {-1, 1}. On va chercher le plus proche voisin de u en terme d'angle et voir quel est cet angle.

Alors frérot, pour choper l'angle entre deux vecteurs, on va utiliser le produit scalaire, t'as vu. On sait que pour deux vecteurs v et w, v·w = ||v|| ||w|| cos(O), où O c'est l'angle entre les deux.

Là, on cherche l'angle max entre u et les potos de M, donc on veut minimiser le cos(O). Les ||v|| et ||w|| sont toujours positifs, donc on s'intéresse au produit scalaire qui doit être le plus petit possible.

On va se concentrer sur les (c_1 ... c_s), parce qu'on sait que les bases canoniques et leurs opposés sont moins "éloignés" en terme d'angle.

Maintenant, on va imaginer u comme un thug qui choisit un camp pour chaque coordonnée, -1 ou 1. Il va choisir le camp le plus faible pour maximiser l'angle avec les (c_1 ... c_s). Du coup, pour chaque coordonnée i, il va prendre la coordonnée opposée au signe de u_i.

En gros, on a construit un vecteur v qui est l'opposé de u pour chaque coordonnée, et on sait que v est dans M. Le produit scalaire u·v = -||u||^2, et donc le cos(O) = -1.

Au final, l'angle entre u et son plus proche voisin est O = arccos(-1) = pi (ou 180 degrés si t'aimes mieux les degrés). Voilà frérot, on a notre angle max, u et son voisin de M sont face à face, prêts à s'affronter comme dans un bon vieux battle royale !

On peut diviser la famille M en trois sous-familles :

M1 : les vecteurs de la base canonique (e1 ... en)
M2 : les vecteurs opposés à ceux de la base canonique (-e1 ... -en)
M3 : les vecteurs dont toutes les coordonnées sont dans {-1,1} (c1 ... cs)

Le vecteur u ne peut pas avoir son plus proche voisin dans M1 ou M2 car pour tout vecteur de ces deux sous-familles, il existe un autre vecteur dans la même sous-famille qui forme un angle opposé avec le premier vecteur. Par conséquent, pour tout vecteur de M1 ou M2, il existe un vecteur dans la même sous-famille qui est aussi proche de u en termes d'angle.

Le vecteur u doit donc avoir son plus proche voisin dans la sous-famille M3. De plus, puisque chaque vecteur de M3 a toutes ses coordonnées égales à -1 ou 1, le vecteur le plus proche de u dans M3 est celui qui a les mêmes valeurs de coordonnées que u, mais avec chaque coordonnée multipliée par le signe de la coordonnée correspondante de u. Autrement dit, le vecteur le plus proche de u dans M3 est le vecteur v=(sign(u1), sign(u2), ..., sign(un)).

Pour trouver l'angle entre u et v, on peut utiliser la formule du produit scalaire :
u . v = ||u|| ||v|| cos(theta)
où ||u|| et ||v|| sont les normes des vecteurs u et v, respectivement, et theta est l'angle entre u et v.

Puisque v a toutes ses coordonnées égales à -1 ou 1, ||v|| = sqrt(s) où s est le nombre de coordonnées de v. De plus, on peut facilement calculer ||u|| = sqrt(u1^2 + u2^2 + ... + un^2).

Enfin, on peut calculer le produit scalaire u . v en utilisant les coordonnées de u et de v :
u . v = u1 sign(u1) + u2 sign(u2) + ... + un sign(un)

Ainsi, on peut calculer cos(theta) :
cos(theta) = (u1 sign(u1) + u2 sign(u2) + ... + un sign(un)) / (sqrt(u1^2 + u2^2 + ... + un^2) sqrt(s))

Finalement, on peut calculer l'angle theta entre u et v :
theta = arccos((u1 sign(u1) + u2 sign(u2) + ... + un sign(un)) / (sqrt(u1^2 + u2^2 + ... + un^2) sqrt(s)))

Le 14 mars 2023 à 20:41:35 :
Wesh la mif, alors là on va se poser dans R^n avec le produit scalaire qui va bien. T'as capté cette famille M de ouf avec les vecteurs de base canonique, leurs opposés et les (c_1 ... c_s) qui ont des coordonnées en {-1, 1}. On va chercher le plus proche voisin de u en terme d'angle et voir quel est cet angle.

Alors frérot, pour choper l'angle entre deux vecteurs, on va utiliser le produit scalaire, t'as vu. On sait que pour deux vecteurs v et w, v·w = ||v|| ||w|| cos(O), où O c'est l'angle entre les deux.

Là, on cherche l'angle max entre u et les potos de M, donc on veut minimiser le cos(O). Les ||v|| et ||w|| sont toujours positifs, donc on s'intéresse au produit scalaire qui doit être le plus petit possible.

On va se concentrer sur les (c_1 ... c_s), parce qu'on sait que les bases canoniques et leurs opposés sont moins "éloignés" en terme d'angle.

Maintenant, on va imaginer u comme un thug qui choisit un camp pour chaque coordonnée, -1 ou 1. Il va choisir le camp le plus faible pour maximiser l'angle avec les (c_1 ... c_s). Du coup, pour chaque coordonnée i, il va prendre la coordonnée opposée au signe de u_i.

En gros, on a construit un vecteur v qui est l'opposé de u pour chaque coordonnée, et on sait que v est dans M. Le produit scalaire u·v = -||u||^2, et donc le cos(O) = -1.

Au final, l'angle entre u et son plus proche voisin est O = arccos(-1) = pi (ou 180 degrés si t'aimes mieux les degrés). Voilà frérot, on a notre angle max, u et son voisin de M sont face à face, prêts à s'affronter comme dans un bon vieux battle royale !

Merci pour la réponse mais je pense que tu n'as pas compris ma question
Je cherche min ( u =/= 0) max (d € M) [ u^T d / (||u|| ||d|| )].
Donc "si un vecteur est le plus éloigné possible de tous les éléments de M, à quel est l'angle entre ce vecteur et son plus proche voisin est-il (s'il a plusieurs plus proches voisins, on en choisit un arbitrairement)?" Clairement, c'est impossible que la réponse soit 180°, rien que dans R^2 on voit bien que c'est faux :

Il n'existe aucun vecteur qui fasse un angle de 180° ou plus avec chacun des vecteurs [1,0], [0,1], [-1,0], [0,-1], [1,1],[-1,-1], [-1,1] et [1,-1].

Le 14 mars 2023 à 20:44:44 :
On peut diviser la famille M en trois sous-familles :

M1 : les vecteurs de la base canonique (e1 ... en)
M2 : les vecteurs opposés à ceux de la base canonique (-e1 ... -en)
M3 : les vecteurs dont toutes les coordonnées sont dans {-1,1} (c1 ... cs)

Le vecteur u ne peut pas avoir son plus proche voisin dans M1 ou M2 car pour tout vecteur de ces deux sous-familles, il existe un autre vecteur dans la même sous-famille qui forme un angle opposé avec le premier vecteur. Par conséquent, pour tout vecteur de M1 ou M2, il existe un vecteur dans la même sous-famille qui est aussi proche de u en termes d'angle.

Avant toute chose, merci pour ta réponse !
Mais j'ai un peu de mal à te suivre. Imaginons par exemple que u = 1.0001*e1, bah clairement son plus proche voisin ça va être e1 qui est dans M1.
Visiblement tu sembles croire que le fait que u a plusieurs plus proches voisins pose problème :
Ce n'est pas le cas, j'aurais dû le spécifier dans mon premier post mais dans l'hypothèse où u a plusieurs plus proches voisins dans M, on s'en fiche: vu qu'ils ont tous le même angle avec u, on donne juste la valeur de cet angle.

Le vecteur u doit donc avoir son plus proche voisin dans la sous-famille M3. De plus, puisque chaque vecteur de M3 a toutes ses coordonnées égales à -1 ou 1, le vecteur le plus proche de u dans M3 est celui qui a les mêmes valeurs de coordonnées que u, mais avec chaque coordonnée multipliée par le signe de la coordonnée correspondante de u. Autrement dit, le vecteur le plus proche de u dans M3 est le vecteur v=(sign(u1), sign(u2), ..., sign(un)).

A l'ordinateur j'ai pu constater qu'en dimension 3-4-5 (et ce fait reste certainement vrai en dimension supérieure) les vecteurs u les plus éloignés possible de M ont au moins une coordonnée nulle, ce cas devrait être pris en compte quand tu parles de signes. Mais bon en soi j'imagine que ça ne change pas grand chose, dans ce cas u aurait juste plusieurs plus proches voisins.

Pour trouver l'angle entre u et v, on peut utiliser la formule du produit scalaire :
u . v = ||u|| ||v|| cos(theta)
où ||u|| et ||v|| sont les normes des vecteurs u et v, respectivement, et theta est l'angle entre u et v.

Ok
En fait on pourrait même raisonner avec des vecteurs normalisés dès le départ : j'ai dit que les vecteurs dans M3 avaient pour coordonnées -1 ou 1 mais j'aurais pu dire directement +-1/sqrt(n). Pareil pour u, j'aurais pu dire directement qu'on le prend unitaire vu que la norme n'a pas d'importance.

Puisque v a toutes ses coordonnées égales à -1 ou 1, ||v|| = sqrt(s) où s est le nombre de coordonnées de v. De plus, on peut facilement calculer ||u|| = sqrt(u1^2 + u2^2 + ... + un^2).

Du coup ||u||=1, ne nous emmerdons pas. Et pour v j'ai pas compris ce que tu racontes, le nombre de coordonnées de v bah c'est n vu qu'on est dans R^n.

Enfin, on peut calculer le produit scalaire u . v en utilisant les coordonnées de u et de v :
u . v = u1 sign(u1) + u2 sign(u2) + ... + un sign(un)

Ainsi, on peut calculer cos(theta) :
cos(theta) = (u1 sign(u1) + u2 sign(u2) + ... + un sign(un)) / (sqrt(u1^2 + u2^2 + ... + un^2) sqrt(s))

Finalement, on peut calculer l'angle theta entre u et v :
theta = arccos((u1 sign(u1) + u2 sign(u2) + ... + un sign(un)) / (sqrt(u1^2 + u2^2 + ... + un^2) sqrt(s)))

Ca me donne pas vraiment de réponse tout ça

on comprend rien tu veux pas screen ton exercice plutôt

Le 14 mars 2023 à 23:06:36 :
on comprend rien tu veux pas screen ton exercice plutôt

J'ai tapé ça proprement en LaTeX.
Noelshack refuse d'héberger mon image, jsp pourquoi. Donc je l'ai mise sur ce site :
https://zupimages.net/viewer.php?id=23/11/wgaa.png

Remarques sur l'image ci-dessus :
-Quand j'écris ||u||, c'est sous-entendu norme euclidienne, norme 2 quoi.
-J'ai normalisé les vecteurs à coordonnées dans {-1, 1} dont je parlais dans le post initial pour simplifier l'énoncé, c'est pour ça que maintenant c'est du " {-1/sqrt(n), 1/sqrt(n)}" .
- "I_n" c'est la base canonique, mais j'imagine que vous l'aviez compris.

Cet exo n'est ni trivial ni de l'algèbre linéaire.

Une autre manière de formuler ton problème est que tu cherches un vecteur de la sphère unité qui minimise max( <u,v>, v dans S), où S est ta famille de vecteurs normalisés.

Le min existe par compacité. Du fait des symétries du problème, on peut trouver un vecteur u maximisant tel que ses coordonnées vérifient u_1>=u_2>= ...>= u_n >= 0.

De plus, un vecteur minimisant doit réaliser son maximum sur n vecteurs de la famille S. Sinon, on pourra trouver un vecteur w orthogonal à u tel que <v,w> <0 pour les k<n vecteurs de S qui réalise le max de <u,v>, et (u+tw)/||u+tw|| aura un max plus petit pour t>0 suffisamment petit.

Du fait des conditions sur u, les vecteurs de S maximisant pour u peuvent être e_1,...,e_k, (e_1+...+e_n)/racine(n), ainsi que d'autres vecteurs du deuxième type si certaines coordonnées de u sont nulles.

A partir d'ici, le résultat dépend de la dimension. Si n>=3 par exemple, on voit que <u,v> ne peut pas prendre la même valeur sur v=e_1, e_2 et (e_1+e_2+e_3)/racine(3), car ça force la dernière coordonnée à être négative.

Pour n=3, le minimum sera réalisé pour un vecteur du type (a,b,0), et on trouve u=(1,racine(3)-1,0)/racine(4-2*racine(3)).

Pour n=4, on se convaint que le minimum devra avoir ses deux dernières coordonnées nulles, et la solution est u=(1,1,0,0)/racine(2).

L op deja t a as mal compris l énoncé par rappoet a la famille C.

De manière plus générale, le vecteur minimisant pourra toujours être choisi de la forme u=(a,a,a..,a,b,0,0,..0) avec a>=b>=0. Soit k le nombre de coordonnées égales à a.

<u,v> prend la même valeur sur e_1,...e_k et sur 1/racine(n)*(e1+...e_k + e_{k+1} +/- .... +/- e_n) ssi

a=(ka+b)/racine(n)

qui a des solutions non nulles a>=b>=0 ssi k<=racine(n).
Pour minimiser <u,v>, on voit qu'il faut prendre k aussi grand que possible, donc k=E(racine(n)), et a et b sont choisis pour vérifier les équations
a=(ka+b)/racine(n)

et ka^2+b^2=1.

Par exemple, quand n=m^2 avec m>=2, le vecteur u est (1,...1,0,...,0)/racine(m), avec m coordonnées égales à 1.

Le 15 mars 2023 à 08:54:26 :

Une autre manière de formuler ton problème est que tu cherches un vecteur de la sphère unité qui minimise max( <u,v>, v dans S), où S est ta famille de vecteurs normalisés.

C est pas le contraire? Il faut d abord qu il trouve le min, puis il trouvera facilement le max après avec l inégalité de cauchy schwarz

Non, minimiser l'angle=maximiser le produit scalaire.

"Pour n=3, le minimum sera réalisé pour un vecteur du type (a,b,0), et on trouve u=(1,racine(3)-1,0)/racine(5-2*racine(3))." (je me suis permis de corriger le dénominateur)

Visuellement ça me semble peu probable (en imaginant (1,sqrt(3)-1,0) dans le carré). Le produit scalaire de u et (1,1,0) est 0,988...

J'aurais tendance à dire que les 3 vecteurs faisant le même angle avec u peuvent être pris comme étant (1,0,0), (1,1,0), (1,1,1). On obtient u = (1,sqrt(2)-1,sqrt(3)-sqrt(2)). Le produit scalaire maximal est 0,886...

Peut-être que ça se généralise suivant cette logique

Le 15 mars 2023 à 12:32:06 :
"Pour n=3, le minimum sera réalisé pour un vecteur du type (a,b,0), et on trouve u=(1,racine(3)-1,0)/racine(5-2*racine(3))." (je me suis permis de corriger le dénominateur)

Visuellement ça me semble peu probable (en imaginant (1,sqrt(3)-1,0) dans le carré). Le produit scalaire de u et (1,1,0) est 0,988...

J'aurais tendance à dire que les 3 vecteurs faisant le même angle avec u peuvent être pris comme étant (1,0,0), (1,1,0), (1,1,1). On obtient u = (1,sqrt(2)-1,sqrt(3)-sqrt(2)). Le produit scalaire maximal est 0,886...

Peut-être que ça se généralise suivant cette logique

Le vecteur (1,1,0) n'est pas dans l'ensemble S.

Eh bah merci pour tes réponses mon khey.
Il est probable que ce résultat finisse dans un papier que je souhaite publier, au milieu d'autres résultats (que j'ai démontré seul, ceux là ). Je veux bien y mentionner ton aide mais j'avoue que ça fait chier d'écrire "Je remercie motocultage pour son aide précieuse"
Si tu veux que je te cite et que tu as un autre pseudo, un alias plus "politiquement correct" tu peux me le donner