3
$\begingroup$

I have two matrices ${\bf{X}}_{p\times r}$ and ${\bf{Y}}_{r\times q}$ with $r<\min(p,q)$. Matrix ${\bf Y}$ does not have full row rank (i.e., rank$({\bf Y})<r$). Can I build two new matrices ${\bf{X}}'_{p\times (r-1)}$ and ${\bf{Y'}}_{(r-1)\times q}$ such that the following three conditions hold:

$\bf{X}' \bf{Y}' = \bf{X} \bf{Y}$

$\|\bf{X}'\|_1 \leq \|\bf{X}\|_1$

$\|\bf{Y}'\|_1 \leq \|\bf{Y}\|_1$

EDIT: By $\ell_1$ norm of a matrix, I mean the sum of absolute values of its elements.

$\endgroup$
4
  • $\begingroup$ What do you mean by $\ell_1$ norm of a matrix? The $\ell_1$ norm of the matrix thought of as a vector? Some sort of induced norm? $\endgroup$
    – Noah Stein
    Jul 28, 2014 at 17:10
  • $\begingroup$ The sum of absolute values of its elements. $\endgroup$
    – Mkl
    Jul 28, 2014 at 17:23
  • $\begingroup$ Do you want an analytic answer, or will a numerical answer suffice? There is a standard-ish numerical way to try to solve these sorts of problems: Fix $X$ and find the $Y^\prime$ with the smallest $r$-th row subject to the constraints $XY^\prime = XY$ and $\|Y^\prime\|_1 \leq \|Y\|$. Then fix this $Y^\prime$ and find the $X^\prime$ with the smallest $r$-th column, and then iterate back and forth between $X$ and $Y$ like this until convergence. If you're lucky, you'll converge to $X^\prime$ with $r$-th column equal to $0$ and $Y^\prime$ with $r$-th row equal to $0$. $\endgroup$ Jul 28, 2014 at 19:31
  • $\begingroup$ Thanks for the comment, but I need an analytical answer; possibly a construction algorithm which builds $X'$ and $Y'$ from $X$ and $Y$, by some row or column operations. $\endgroup$
    – Mkl
    Jul 29, 2014 at 16:40

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.