For what $X$ do we have $\|XA\|_{1} \leq 1$ for a given $\|A\|_{1} \leq 1$.

Question

All matrices are real.

By $\| \cdot \|_1$ I mean a matrix norm induced by the vector norm $L_1$, i.e. the max of the column sums of absolute values.

The matrix $A$ is given and we have $\|A\|_{1} \leq 1$.

Is there a nice characterization of the set of matrices $X$ for which we have $\|XA\|_{1} \leq 1$?

I see two sufficient conditions:

1. $\|X\|_{1} \leq 1$, (edit) which can be sharpened to $\|X\|_{1} \leq \frac{1}{\|A\|_{1}}$
2. X is an oblique projection on some space that includes the column space of $A$.

But neither of them is necessary. Is there a nice characterization of the set of matrices that meet this condition (like they have common form or something like that)?

Answer 1

Let ${\mathbb M}_n$ be equipped with $\| \cdot \|_1$. Denote by $B_1=\{ X\in {\mathbb M}_n;\quad \| X\|_1\leq 1\}$, the closed unit ball in ${\mathbb M}_n$. For $A\in {\mathbb M}_n$, let $\rho_A:{\mathbb M}_n \to {\mathbb M}_n$ be defined by $\rho_A(X)=XA$. Then the problem is to describe the set $$ \rho_{A}^{-1}(B_1)=\{ X\in {\mathbb M}_n;\quad \rho_A(X)\in B_1\}. $$

I do not know if the complete answer to this question can be given. So I will mention only to observations.

(1) If $A$ is invertible, then $\rho_A$ is a bijection and its inverse is $\rho_{A^{-1}}$. Hence, in this case $$\rho_{A}^{-1}(B_1)=\rho_{A^{-1}}(B_1)=\{ XA^{-1};\quad X\in B_1\}. $$ (2) If $A$ is not invertible, then $0$ is its eigenvalue and there exist vectors $x\ne 0$ such that $A^Tx=0$. Hence $x^TA=0$ which implies that $XA=0$ for $X=yx^T$, where $y$ is an arbitrary vector. Of course, any linear combination of matrices of this type is in $\rho_{A}^{-1}(B_1)$. Moreover, if $x_1, \ldots, x_k$ are eigenvectors for $A^T$ at $0$ and $y_1, \ldots, y_k$ are arbitrary vectors, then for each $T\in \rho_{A}^{-1}(B_1)$ one has $$ X=y_1 x_{1}^{T}+\cdots+y_k x_{k}^{T}+T \in \rho_{A}^{-1}(B_1).$$ Thus in this case $\rho_{A}^{-1}(B_1)$ contains the subspace of matrices which I will denote (maybe not correct) as ${\mathbb R}^n \otimes (ker A^T)$.

Example Let $A=diag[\lambda_1, \ldots, \lambda_n]$ (diagonal matrix) with $\| A\|_1 \leq 1$. Then $|\lambda_i|\leq 1$ for any $1\leq i \leq n$. Denote $\epsilon_i=\frac{1}{\lambda_i}$ if $\lambda_i \ne 0$ and $\epsilon_i=+\infty$ if $\lambda_i=0$. Write a matrix $X\in {\mathbb M}_n$ as $$ X=\bigl[x_1|\ldots|x_n\bigr], $$ where $x_i$ is the $i$th column vector. Then $$\rho_{A}^{-1}(B_1)=\{ X=\bigl[x_1|\ldots|x_n\bigr]\in {\mathbb M}_n;\quad \| x_i\|_1 \leq \epsilon_i \quad (1\leq i \leq n)\}. $$

Answer 2

I guess it holds for $\|X\|_{1}\leq \frac{1}{\|A\|_{1}}$. Let $A$ be a $m\times n$ matrix. Then $A^{T}:\mathbb{R}^{m}\to\mathbb{R}^{n}$ is a linear map. Now if we consider the $\ell_{\infty}$ norm on both $\mathbb{R}^{m}$ and $\mathbb{R}^{n}$, then $\|A\|_{1}=\|A^{T}\|_{op}$, where $\|\cdot\|_{op}$ stands for the operator norm. Therefore \begin{eqnarray} \|XA\|_{1}=\|A^{T}X^{T}\|_{op}\leq\|X^{T}\|_{op}\|A^{T}\|_{op}=\|X\|_{1}\|A\|_{1}. \end{eqnarray} If $\|X\|_{1}\leq \frac{1}{\|A\|_{1}}$, then we have $\|XA\|_{1}\leq 1$.