Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.