¿Qué matrices doblemente estocásticas pueden escribirse como productos de matrices de promedios por pares?

Question

Una matriz $A$ se denomina doblemente estocástica si sus entradas son no negativas y si todas sus filas y columnas suman $1$ . Un subconjunto de matrices doblemente estocásticas es el conjunto de matrices de promediado por pares que acercan dos componentes de un vector a su media. Más concretamente, una matriz de promediación por pares $P_{i,j,\alpha}$ se define estipulando que $y=P_{i,j,\alpha}x$ es $$ y_i = (1-\alpha) x_i + \alpha x_j$$ $$ y_j = \alpha x_i + (1-\alpha) x_j$$ $$ y_k = x_k ~~{\rm for~ all }~ k \neq i,j~,$$ donde $\alpha \in [0,1]$ .

Mi pregunta es: ¿toda matriz doblemente estocástica puede escribirse como un producto de matrices de promedios por pares?

Si la respuesta es negativa, me gustaría saber si es posible caracterizar las matrices doblemente estocásticas que se pueden escribir de esta manera.

Actualización: Acabo de darme cuenta de que la respuesta es no. He aquí un esbozo de la prueba. Elija cualquier $3 \times 3$ matriz doblemente estocástica $A$ con $A_{23}=A_{32}=0$ . Si $A$ puede escribirse como el producto de medias por pares, las matrices de medias por pares $P_{2,3,\alpha}$ nunca aparecen en el producto, ya que dan lugar a la fijación del $(2,3)$ y $(3,2)$ entradas a números positivos, que siguen siendo positivos después de más aplicaciones de medias por pares. Por tanto, el producto sólo debe utilizar $P_{1,2,\alpha}$ o $P_{1,3,\alpha}$ . Pero se puede ver que no importa en qué orden se apliquen estas matrices, al menos una de $A_{23}$ o $A_{32}$ se fijará en un número positivo. Por ejemplo, si promediamos primero 1 y 2 y luego 1 y 3, entonces $A_{32}$ será distinto de cero.

Mi segunda pregunta sigue sin respuesta: ¿es posible caracterizar las matrices que son productos de medias por pares?

Answer 1

Esta cuestión se ha estudiado aquí (pero no se da ninguna caracterización)

Marcus, Marvin; Kidman, Kent; Sandy, Markus. Productos de matrices elementales doblemente estocásticas. Linear and Multilinear Algebra 15 (1984), no. 3-4, 331-340.

Obsérvese también que si consideramos la familia de matrices con filas y columnas que suman 1 (pero permiten entradas negativas) y $\alpha \in \mathbf{R}$ el resultado correspondiente es verdadero, véase

Johnsen, E. C. Matrices esencialmente doblemente estocásticas. III. Productos de matrices elementales. Linear and Multilinear Algebra 1 (1973), no. 1, 33-45.

Answer 2

Puede ser demasiado difícil caracterizar todas las matrices que son productos de matrices promediadas por pares, por lo que probablemente sea una buena idea intentar resolver un problema más fácil (al menos computacionalmente) en un monoide cociente para obtener y computar muchos contraejemplos.

Sea $[n]=\{1,\dots,n\}$ . Si $f\in S_{n}$ entonces $\rho_{f}$ denota la matriz de permutación $(\delta_{f(i),j})_{i,j}$ que corresponde a la permutación $f$ . Supongamos que $A\subseteq[n]\times[n]$ . Entonces decimos que $A$ es un $n\times n$ -multipermutación si $A$ es la unión de permutaciones. Sea $M_{n}$ sea el conjunto de todos los $n\times n$ -multipermutaciones. Sea $V_{n}=P([n]^{2})$ y definir una operación de composición en $V_{n}$ por $$A\circ B=\{(x,z)|\exists y,(x,y)\in B,(y,z)\in A\}.$$ Sea $DS_{n}$ sea el conjunto de todas las matrices doblemente estocásticas. Definir un mapeo $\phi:DS_{n}\rightarrow M_{n}$ dejando $\phi((a_{i,j})_{i,j})=\{(i,j)\mid a_{i,j}>0\}$ . Entonces $\phi$ es un antihomorfismo monoide suryectivo (es decir. $\phi(BA)=\phi(A)\circ\phi(B)$ para doble estocástico $A,B$ y $\phi$ preserva la identidad).

Sea $B_{n}$ sea el submonoide de $M_{n}$ generado por elementos de la forma $f\cup g$ para algunos $f,g\in S_{n}$ . Entonces $R\in B_{n}$ sólo si $R=\phi(A)$ para alguna matriz $A$ que puede factorizarse como un producto de matrices de promedios por pares. Por lo tanto, si podemos demostrar que $\phi(A)\not\in B_{n}$ entonces sabemos que $A$ no puede factorizarse como un producto de matrices de promedios por pares.

Ahora, cada elemento de $B_{n}$ se puede poner en la forma $(1\cup f_{1})\circ\dots\circ(1\cup f_{r})\circ g$ o en la forma $u\circ (1\cup v_{1})\circ\dots\circ(1\cup v_{r})$ . Si definimos $B_{n}^{\sharp}$ sea el submonoide de $B_{n}$ generado por los elementos de la forma $1\cup f$ entonces $B_{n}$ puede considerarse una especie de producto semidirecto del grupo de permutaciones $S_{n}$ y el monoide $B_{n}^{\sharp}$ . De hecho, si definimos una operación monoide $*$ en $V_{n}\times S_{n}$ dejando $(R,f)*(S,g)=(RfSf^{-1},fg)$ y definimos un homomorfismo monoide $\Gamma:V_{n}\times S_{n}\rightarrow V_{n}$ dejando $\Gamma(R,f)=Rf$ entonces $B_{n}=\Gamma[B_{n}^{\sharp}\times S_{n}]$ .

Sea $D_{n}=\{(R,(R\circ(1\cup f)))\mid R\in V,f\in S_{n}\}$ . Entonces $G_{n}=(V_{n},D_{n})$ es un grafo acíclico, por lo que podemos ordenar parcialmente $V_{n}$ dejando $f\leq g$ si y sólo si existe un camino dirigido desde $f$ a $g$ . Además, la ordenación parcial $\leq$ es compatible con $\subseteq$ ya que si $f\leq g$ entonces $f\subseteq g$ (esto es útil ya que $\leq$ es difícil de calcular, pero $\subseteq$ es fácil de calcular). Obsérvese que $R$ pertenece a $B_{n}$ si y sólo si existe algún camino desde alguna permutación $f$ a $R$ en $(V_{n},D_{n})$ . Defina $\downarrow R=\{S\in V_{n}\mid S\subseteq R\}$ . Dado que todo camino desde $f$ a $R$ sólo atraviesa los nodos del conjunto $\downarrow R$ podemos restringir nuestro algoritmo de búsqueda de caminos al subgrafo inducido cuyos nodos son precisamente los elementos de $\downarrow R$ . Por lo tanto, $R\in B_{n}$ si y sólo si existe alguna permutación $f$ y una ruta desde $f$ a $R$ en el subgrafo inducido $G_{n}[\downarrow R]$ .

Ahora, observe que $$N_{G_{n}[\downarrow S]}(R)=\{R\circ(1\cup f)\mid f\in S_{n},R\circ(1\cup f)\subseteq S\}=\{R\circ(1\cup f)\mid f\in S_{n},R\circ f\subseteq S\}.$$ Por lo tanto, para calcular, $N_{G_{n}[\downarrow S]}(R)$ basta con encontrar todas las permutaciones $f\in S_{n}$ tal que $R\circ f\subseteq S$ . Sin embargo, si definimos $T_{y}=\{z\in[n]\mid\forall x,(x,y)\in R\rightarrow(x,z)\in S\}$ entonces $R\circ f\subseteq S$ sólo si $f(y)\in T_{y}$ para todos $y\in[n]$ . Por lo tanto, el problema de encontrar los elementos en $N_{G_{n}[\downarrow S]}(R)$ se reduce al problema de encontrar todos los emparejamientos perfectos en grafos bipartitos. Sin embargo, según este documento el problema de encontrar todas las correspondencias perfectas en un grafo bipartito requiere $O(c(n+m)+n^{5/2})$ esfuerzo computacional y $O(nm)$ memoria donde $n$ es el número de vértices, $m$ es el número de aristas, y $c$ es el número de emparejamientos perfectos en el grafo bipartito. Sin embargo, no estoy convencido de que encontrar todas las biyecciones $f$ con $R\circ f\subseteq S$ es la mejor estrategia para informática $N_{G_{n}[\downarrow S]}(R)$ ya que puede haber muchas más permutaciones $f$ con $R\circ f\subseteq S$ que elementos en $N_{G_{n}[\downarrow S]}(R)$ .

Un gráfico mejorado

Definir un gráfico $G_{n,S}=(V_{n,S},E_{n,S})$ donde

1. $V_{n,S}$ se compone de tuplas $(P,A,B,Q)$ tal que $|A|=|B|$ y $Q\subseteq R\cap(B^{c}\times[n])$ .

2. $E_{n,S}$ está formado por las aristas de las siguientes formas

i. $((P,[n],[n],\emptyset),(P,\emptyset,\emptyset,P))\in E_{n,S}$

ii. Supongamos que $A\subseteq[n],B\subseteq[n]$ y $a\in A^{c},b\in B^{c}$ . Entonces $$((P,A,B,Q),(P\cup(Q\circ\{(a,b)\}),A\cup\{a\},B\cup\{b\},Q\setminus(\{b\}\times[n])))\in E_{n,S}$$ tal que $P\cup(Q\circ\{(a,b)\})\subseteq S$ .

Supongamos que $f$ es una permutación. Entonces hay un camino dirigido desde $(f,\emptyset,\emptyset,f)$ a $(P,A,B,Q)$ si y sólo si hay $g_{1},\dots,g_{r}$ tal que si $R=f\circ(1\cup g_{1})\circ\dots\circ(1\cup g_{r})$ entonces hay una cierta biyección $h:A\rightarrow B$ tal que $P=R\cup(R\circ h)$ y $Q=R\cap(B^{c}\times[n])$ . Por lo tanto, $S\in B_{n}$ si y sólo si existe un camino desde $(f,\emptyset,\emptyset,f)$ a $(S,\emptyset,\emptyset,S)$ para alguna permutación $f$ con $f\subseteq S$ .

Por lo tanto, se puede determinar si $S\in B_{n}$ mediante un algoritmo de búsqueda de trayectorias. Sin embargo, nuestro algoritmo de búsqueda de caminos probablemente no será muy eficiente en este punto, así que reduzcamos el número de aristas de $(f,\emptyset,\emptyset,f)$ a $(S,\emptyset,\emptyset,S)$ para mejorar la eficacia. Decimos que un subconjunto $E\subseteq E_{n,S}$ es transitable si $E$ contiene cada arista de la forma $((P,[n],[n],\emptyset),(P,\emptyset,\emptyset,P))$ y donde si $(P,A,B,Q)\in V_{n,S}$ y $A\neq[n]$ y $h:A^{c}\rightarrow B^{c}$ es biyectiva, entonces hay $a\in A^{c},b\in B^{c}$ con $b=h(a)$ y donde $$((P,A,B,Q),(P\cup(Q\circ\{(a,b)\}),A\cup\{a\},B\cup\{b\},Q\setminus(\{b\}\times[n])))\in E.$$

Obsérvese que si $E$ es transitable, entonces $S\in B_{n}$ si y sólo si existe algún camino desde $(f,\emptyset,\emptyset,f)$ a $(S,\emptyset,\emptyset,S)$ en el grafo dirigido $(V_{n,S},E)$ por lo que se puede utilizar un algoritmo de búsqueda de caminos para determinar si $S\in B_{n}$ o no.

Código

Este es el código en GAP para determinar si $R\in B_{n}$ . No he hecho ningún intento de optimizar este código.

`allperms:=function(x) local list,n,table,i,newtable,j; n:=Length(x); table:=[[]]; for i in [1..n] do newtable:=[]; for list in table do for j in [1..n] do if j in list then continue; fi; if x[i][j]=1 then Add(newtable,Concatenation(list,[j])); fi; od; od; table:=newtable; od; return table; end;

implicator:=function(x,y) local n,z,i,j,k; n:=Length(x); z:=x*0; for i in [1..n] do for j in [1..n] do z[i][j]:=1; for k in [1..n] do if y[k][j]=0 and x[k][i]=1 then z[i][j]:=0; break; fi; od; od; od; return z; end;

neighbors:=function(x,y) local list,n,xx,z,perms,output,i,j; n:=Length(x); z:=implicator(x,y); perms:=allperms(z); output:=[]; for list in perms do xx:=StructuralCopy(x); for i in [1..n] do for j in [1..n] do if x[i][j]=1 then xx[i][list[j]]:=1; fi; od; od; Add(output,xx); od; return output; end;

size:=function(x) return Sum(List(x,Sum)); end;

test:=function(y) local a,perms,xx,n,s,i,j,tar,table,har,bb,qq; n:=Length(y); s:=size(y); perms:=allperms(y); tar:=NewDictionary(true,true); table:=[];

for a in perms do xx:=y*0; for i in [1..n] do xx[i][a[i]]:=1; od; Add(table,xx); AddDictionary(tar,xx,true); od;

while Length(table)>0 do qq:=Remove(table); har:=neighbors(qq,y); for bb in har do if size(bb)=s then return true; fi; if not (LookupDictionary(tar,bb)=true) then AddDictionary(tar,bb,true); Add(table,bb); fi; od; od; return false; end;

`

Más códigos

Este es el código que encuentra un camino en el grafo $(V_{n,S},E)$ para algún conjunto travertible $E$ .

`newnode:=function(quadruple) local PP; PP:=quadruple[1]; return [PP,[],[],PP]; end;

testquad:=function(quadruple,pair,y) local a,b,P,Q,A,B,n,i; a:=pair1; b:=pair[2]; P:=quadruple1; A:=quadruple[2]; B:=quadruple[3]; Q:=quadruple[4]; n:=Length(P); for i in [1..n] do if Q[b][i]=1 and y[a][i]=0 then return false; fi; od; return true; end;

newpairzero:=function(n,zero,one) local m,l,lar,mar; m:=Length(zero); lar:=Difference([1..n],zero); mar:=Difference([1..n],one); l:=Minimum(lar); m:=Minimum(mar); return List(mar,v->[l,v]); end;

newpairone:=function(n,zero,one) local m,l,lar,mar; m:=Length(zero); lar:=Difference([1..n],zero); mar:=Difference([1..n],one); l:=Minimum(lar); m:=Minimum(mar); return List(lar,v->[v,m]); end;

extendpair:=function(quadruple,pair) local a,b,P,Q,A,B,n,i,AA,BB,PP,QQ; a:=pair1; b:=pair[2]; P:=quadruple1; A:=quadruple[2]; B:=quadruple[3]; Q:=quadruple[4]; n:=Length(P); QQ:=StructuralCopy(Q); AA:=Concatenation(A,[a]); BB:=Concatenation(B,[b]); Sort(AA); Sort(BB); PP:=StructuralCopy(P); for i in [1..n] do PP[a][i]:=Maximum(QQ[b][i],PP[a][i]); QQ[b][i]:=0; od; return [PP,AA,BB,QQ]; end;

test:=function(y) local P,Q,pair,list,n,tar,table,xx,i,j,A,B,quadruple; n:=Length(y); tar:=NewDictionary(true,true); table:=[]; xx:=[]; for i in [1..n] do xx[i]:=[]; for j in [1..n] do xx[i][j]:=0; od; xx[i][i]:=1; od; Add(table,[xx,[],[],xx]); while Length(table)>0 do quadruple:=Remove(table); if not LookupDictionary(tar,quadruple)=fail then continue; fi; AddDictionary(tar,quadruple,true); P:=quadruple1; A:=quadruple[2]; B:=quadruple[3]; Q:=quadruple[4]; if Length(A)=n then if P=y then return true; fi; Add(table,newnode(quadruple)); else list:=newpairzero(n,A,B); for pair in list do if testquad(quadruple,pair,y) then Add(table,extendpair(quadruple,pair)); fi; od; fi; od;

return false; end;

`

Observaciones empíricas

Ejecuté el algoritmo anterior para determinar si los elementos pertenecían a $B_{n}$ y la mayoría de los elementos de $M_{n}$ que he probado no pertenecen a $B_{n}$ . De hecho, en la mayoría de los casos, los elementos de la forma $f\cup g\cup h$ donde $f,g,h\in S_{n}$ no pertenecen a $B_{n}$ por lo que la mayoría de las matrices estocásticas de la forma $\frac{1}{3}(\rho_{f}+\rho_{g}+\rho_{h})$ no pueden escribirse como el producto de matrices de promediación por pares.

Probablemente añadiré detalles y mejoraré esta respuesta más adelante con el fin de mejorar el algoritmo para determinar si un elemento $R\in V_{n}$ pertenece a $B_{n}$ o no.

Matrices singulares

Supongamos que $f$ es una permutación que puede escribirse como la composición de $r$ ciclos disjuntos de longitudes $k_{1},\dots,k_{r}$ .

Entonces $$\text{Det}(t\cdot 1_{n}+(1-t)\rho_{f})=\prod_{j=1}^{r}[t^{k_{j}}+(t-1)^{k_{j}}].$$ En particular, $t\cdot 1_{n}+(1-t)\rho_{f}$ es no singular si y sólo si $t=1/2$ y si $t=1/2$ entonces $\text{Rank}(t\cdot 1_{n}+(1-t)\rho_{f})$ es el número de ciclos Impares en la permutación $f$ .

Si $R\in B_{n}$ entonces $N(R)$ sea la suma de todas las sumas $m_{1}+\dots+m_{r}$ tal que $R=f(1+g_{1})\dots(1+g_{r})$ y cuando $g_{i}$ se escribe como una composición disjunta de ciclos, $m_{i}$ de esos ciclos son impar. Si $R\not\in B_{n}$ a continuación, establezca $N(R)=\infty$ . Podemos ajustar nuestro algoritmo para determinar si $R\in B_{n}$ o no para que calcule el valor $N(R)$ también.

Obsérvese entonces que si $A$ es una matriz doblemente estocástica que puede escribirse como un producto de matrices de promedios por pares, entonces $\text{Null}(A)\leq N(\phi(A))$ . Por lo tanto, si $\text{Null}(A)>N(\phi(A))$ entonces sabemos que $A$ no puede escribirse como producto de matrices de promedios por pares.

Matrices doblemente estocásticas cerca de una matriz de permutación

El problema de determinar si $R\in B_{n}^{\sharp}$ o no es más fácil de resolver que el problema de determinar si $R\in B_{n}$ ya que para $B_{n}^{\sharp}$ el algoritmo de búsqueda de trayectorias comienza con un único vértice, a saber $(1,\emptyset,\emptyset,1)$ en lugar de muchos vértices. Afortunadamente, el problema de determinar si un conjunto pertenece a $B_{n}^{\sharp}$ nos ayuda a demostrar que ciertas matrices doblemente estocásticas no pueden escribirse como un producto de matrices de promedios por pares.

Si $A$ es una matriz doblemente estocástica que se parece demasiado a una matriz de permutación $\rho_{f}$ y $A$ puede escribirse como un producto de matrices de promedios por pares, entonces sabemos que $A$ se puede poner en la forma $A=\rho_{f}(t_{1}I_{n}+(1-t_{1})\rho_{g_{1}})\dots(t_{r}I_{n}+(1-t_{r})\rho_{g_{r}})$ para constantes $t_{1},\dots,t_{r}\in(0,1)$ donde las constantes $t_{1},\dots,t_{r}$ están cerca $1$ . Precisemos esta intuición.

Teorema: Sea $\|\cdot\|$ sea una norma sobre el espacio vectorial de todos los $n\times n$ -matrices. Sea $$M=\max_{f\in S_{n}}\|\rho_{f}\|,$$ y que $$N=\min_{f\in S_{n}\setminus\{1\}}\|I_{n}-\rho_{f}\|.$$ Entonces, siempre que $A$ es el producto de matrices de promedios por pares, entonces

1. $$A=(t_{1}I_{n}+(1-t_{1})\rho_{f_{1}})\cdots(t_{r}I_{n}+(1-t_{r})\rho_{f_{r}})$$ donde $\min(t_{1},\dots,t_{r})\geq 1/2$

o

2. $$\|A-I_{n}\|\geq N-2M(1-|\det(A)|).$$

Prueba: Supongamos que $f$ es una permutación que puede descomponerse en ciclos disjuntos de longitudes $k_{1},\dots,k_{r}$ . Observe que $$|\det(tI_{n}+(1-t)\rho_{f})|=\prod_{j=1}^{r}|t^{k_{j}}+(t-1)^{k_{j}}| \leq|t^{k_{1}}+(t-1)^{k_{1}}|$$ $$\leq t^{k_{1}}+(1-t)^{k_{1}}\leq t^{2}+(1-t)^{2}\leq\frac{1}{2}+|t-\frac{1}{2}|.$$

Ahora, supongamos que $A$ es el producto de matrices de promediación por pares. Entonces, sin pérdida de generalidad, hay $t_{1},\dots,t_{r}$ tal que $\min(t_{1},\dots,t_{r})\geq\frac{1}{2}$ junto con permutaciones $f,g_{1},\dots,g_{r}$ donde $$A=\rho_{f}(t_{1}I_{n}+(1-t_{1})\rho_{g_{1}})\dots(t_{r}I_{n}+(1-t_{r})\rho_{g_{r}})$$ .

En este caso, tenemos $\det(A)\leq t_{1}\dots t_{r}$ .

Ahora, $$\|A-\rho_{f}\|\leq\|A-\rho_{f}t_{1}\dots t_{r}I_{n}\|+\|\rho_{f}t_{1}\dots t_{r}I_{n}-\rho_{f}\|$$ $$\leq(1-t_{1}\dots t_{r})M+(1-t_{1}\dots t_{r})M\leq 2M(1-t_{1}\dots t_{r})\leq 2M(1-\det(A)).$$

Por lo tanto, $$\|A-I_{n}\|\geq\|I-\rho_{f}\|-\|A-\rho_{f}\|\geq N-2M(1-\det(A)).$$ Q.E.D.

Observe que $M=\max\{\|A\|:\text{$ A $ is doubly stochastic}\}$ . Además, $\|N\|\leq\|I_{n}\|+M\leq 2M$ . Si la norma $\|\cdot\|$ es submultiplicativa ( $\|AB\|\leq\|A\|\cdot\|B\|$ para todos $A,B$ ), entonces $M=\|I\|=I_{n},\|N\|\leq 2$ .

Teorema: Sea $\|\cdot\|$ sea una norma sobre el conjunto de todos los $n\times n$ -matrices. Sea $$M=\max_{f\in S_{n}}\|\rho_{f}\|,N=\min_{f\in S_{n}\setminus\{1\}}\|I_{n}-\rho_{f}\|.$$

Supongamos que $A$ es una matriz doblemente estocástica. Si $\phi(A)\not\in B_{n}^{\sharp}$ y $$|A-I_{n}|<N-2M(1-\det(A)),$$ entonces $A$ no puede ser como el producto de matrices de promediación por pares.

Argumento de la dimensionalidad

Supongamos que $R\in B_{n}$ . Entonces $T_{R}$ sea el subespacio vectorial de $M_{n}(\mathbb{R})$ formado por todas las matrices $(a_{i,j})_{i,j}$ tal que $\{(i,j)\mid a_{i,j}\neq 0\}\subseteq R$ y donde $\sum_{k}a_{i,k}=0$ para cada $i\in[n]$ y donde $\sum_{k}a_{k,j}=0$ para cada $i\in[n]$ . Observe que $\dim(T_{R})\geq|R|-2n$ .

Entonces, siempre que $\phi(A)=R$ existe un subconjunto abierto $U$ de $T_{R}$ tal que $A+B$ es doblemente estocástica para cada $B\in U$ .

Proposición: Supongamos que $R\subseteq[n]^{2}$ , $R$ es la unión de permutaciones, pero $R$ no se puede poner en la forma $R=f(1\cup f_{1})\dots(1\cup f_{r})$ donde $f_{1},\dots,f_{r}$ son permutaciones no idénticas y $f$ es una permutación, y donde $r\geq\dim(T_{R})$ . Entonces existe una matriz doblemente estocástica $A$ con $\phi(A)=R$ pero dónde $A$ no puede escribirse como producto de matrices doblemente estocásticas.

Prueba: Basta observar que la dimensión del conjunto de todas las matrices doblemente estocásticas $A$ con $\phi(A)=R$ es $\dim(T_{R})$ mientras que la dimensión del conjunto de todos los productos de matrices promediadas por pares $A$ con $\phi(A)=R$ es como máximo $\dim(T_{R})-1$ . Q.E.D.

Answer 3

Sea $DS_{n}$ denota el conjunto de todos los $n\times n$ matrices doblemente estocásticas. Sea $F_{n}$ denota el conjunto de todos los $n\times n$ matrices que pueden escribirse como productos de matrices de promedios por pares. Entonces afirmo que $F_{n}\subseteq\overline{F_{n}^{\circ}}$ donde el interior y el cierre se toman en el conjunto $DS_{n}$ . Por lo tanto, $F_{n}\setminus F_{n}^{\circ}$ no es denso en ninguna parte de $DS_{n}$ . En particular, si $F_{n}$ está cerrado, entonces $F_{n}$ debe estar regularmente cerrado. Todavía no sé si $F_{n}$ es un conjunto cerrado de not.

Sea $DS_{n}^{\sharp}$ sea el conjunto de todos los $n\times n$ matrices con entradas de valor real en las que la suma de cada fila es $1$ y la suma de cada columna es también $1$ . Sea $T_{n}$ sea el conjunto de todos los $n\times n$ matrices con entradas de valor real en las que la suma de cada fila es $0$ y la suma de cada columna es también $0$ . En otras palabras, $DS_{n}^{\sharp}$ es el conjunto de todas las matrices generalizadas doblemente estocásticas, y $T_{n}$ es el espacio tangente de cada punto de $DS_{n}^{\sharp}$ .

Observamos que $\dim(T_{n})=(n-1)^{2}$ y $T_{n}$ está generado por elementos de la forma $\rho(f)-I_{n}$ donde $\rho(f)$ es la matriz de permutación que corresponde a la permutación $f$ . Sea $r=n^{2}$ . Hay permutaciones $f_{1},\dots,f_{r}$ donde $\rho(f_{1})-I_{n},\dots,\rho(f_{r})-I_{n}$ es una base para $T_{n}$ .

Afirmo que siempre que $A\in F_{n}$ y $\epsilon>0$ existe un subconjunto abierto $U\subseteq DS_{n}^{\sharp}$ y algunos $B\in\overline{U}$ con $\|A-B\|<\epsilon$ .

Supongamos que $A\in F_{n}$ . Sea $\epsilon>0$ . Entonces existe una matriz invertible $B\in F_{n}$ con $\|A-B\|<\epsilon$ .

Definir una función $C:\mathbb{R}^{n}\rightarrow DS_{n}^{\sharp}$ dejando $$C(t_{1},\dots,t_{r})=B((1-t_{1})I_{n}+t_{1}\rho(f_{1}))\dots((1-t_{r})I_{n}+t_{r}\rho(f_{r})).$$

Ahora bien, si $1\leq i\leq n$ entonces $$\frac{\partial}{\partial t_{i}}C(t_{1},\dots,t_{r})|_{(t_{1},\dots,t_{r})=0}=B\cdot(\rho(f_{i})-I_{n}).$$

Ahora bien, puesto que $B$ es invertible, resulta que los vectores de la forma $$\frac{\partial}{\partial t_{i}}C(t_{1},\dots,t_{r})|_{(t_{1},\dots,t_{r})=0}=B\cdot(\rho(f_{i})-I_{n})$$ forman una base del espacio tangente $T_{n}$ . Por lo tanto, por el teorema de la función inversa, podemos concluir que existe un subconjunto abierto $U\subseteq\mathbb{R}^{n}$ con $(0,\dots,0)\in U$ tal que si $V=C[U]$ entonces $C$ mapas $U$ difeomórficamente en $V$ y donde $V$ es un subconjunto abierto de $DS_{n}^{\sharp}$ . Obsérvese además que $B=C(0,\dots,0)$ . Sea $$U_{1}=\{(x_{1},\dots,x_{n})\in U\mid\max(x_{1},\dots,x_{n})<1,\min(x_{1},\dots,x_{n})>0\}.$$ Entonces hay algo abierto $V_{1}\subseteq V$ tal que $C$ mapas $U_{1}$ difeomórficamente en $V_{1}$ y donde $B\in\overline{V_{1}}$ . Sin embargo, $V_{1}$ es un subconjunto abierto de $DS_{n}^{\sharp}$ consistente únicamente en productos de matrices de promedios por pares.