Sign up ×

Let $A\overline{X}=0$, where $A=(a_{i,j})\in M_{L, n}(\mathbb{C})$ is a given non-zero $L\times n$ matrix over the complex numbers $\mathbb{C}$, and $\overline{X}=(x_1, x_2, \cdots, x_n)^T $ is an $n$-column vector.

Suppose $L< n$, then we know that the above equations have non-zero solutions. My question is:

What are the sufficient (and necessary) conditions on $A$ such that we can find one solution $\overline{X}$ satisfying:

$$(P)\ \ \ \ \ \ \ \ |x_1|>\sum_{i=2}^n|x_i|$$

Here are some observations and remarks:

  1. We may assume $L>1$, since for $L=1$, $|a_{1,1}|<|a_{1,i}|$ for some $i>1$ is a sufficient condition.

  2. For $a_{i,1}\neq 0$, since $x_1=-\sum_{j=2}^n\frac{a_{i,j}x_j}{a_{i,1}}$, we know that a necessary condition for the property $(P)$ to be hold is that $\exists j>1$, s.t., $|a_{i,j}|>|a_{i,1}|$.

  3. My primary motivation to ask this question is that I want to consider equations in the general group algebras $\mathbb{Z}G$ for some countable discrete group $G$; see this problem: Find a special element in group algebra

share|cite|improve this question

1 Answer 1

This is not really a full answer.

Split the matrix into the first column and the rest, so that $A=(A_1,A_2)$. We can set $x_1=-1$ by scaling, so that the problem is to find a solution to $$ A_2 x = A_1, \quad \|x\|_1<1. $$ A necessary condition is clearly that $$ \|A_1\|_1 = \|A_2x\|_1 < \|A_2\|_1. $$

The problem of finding a solution to $A_2x=A_1$ that minimizes $\|x\|_1$ instead of bounding it above is $\ell_1$-regularized least squares, but I don't know a good bound.

If we minimize $\|x\|_2$ instead, then this is an underdetermined least squares problem, so in the case that $A_2$ has full rank, the solution with the smallest 2-norm gives the sufficient condition that $$ \|A_2^t(A_2A_2^t)^{-1}A_1\|_1 < 1. $$

share|cite|improve this answer

Your Answer


