Questions tagged [rank-1-matrices]
The rank-1-matrices tag has no usage guidance.
70 questions
2
votes
2
answers
68
views
Completing a rank-1 decomposition of a matrix
Let $M$ be an $m\times n$ matrix of rank $r$. I am interested to express $M$ as $C_1 + \ldots + C_r$ where each $C_i$ is a rank-1 matrix. How many $C_i$'s of rank-1 am I allowed to fix (if any) and ...
- 166
2
votes
0
answers
83
views
stability of rank one perturbation of stochastic matrix
Let $I$ be the identity matrix and $P$ be an irreducible $n$ by $n$ row stochastic matrix. Let $d$ be a stochastic (column) vector and $e$ be an all one (column) vector. Let $t > 0$ be a real ...
- 145
0
votes
0
answers
20
views
the eigenvalue of the combination of multiplicative and additive rank 1 perturbation
Given:
$A$ and $B$ are both rank 1 matrices. They are both Hermitian.
Invetigate:
The eigenvalue of $A(B+sI)^{0.5}$.
I figured out that the eigenvalue of $A(A+sI)^{0.5}$ has a closed form of $y^H x \...
- 1
1
vote
1
answer
77
views
Showing existence of symplectic transformations preserving a quadratic form
Question: I need help to prove the following statement.
Let $W_i:=w_iw_i^T\in\mathbb{R}^{n\times n}$, for $n$ even, be symmetric rank-1 matrices, $J=-J^T$ the canonical symplectic matrix and define ...
- 140
1
vote
0
answers
14
views
bound for SR1 update
Suppose the exact hessian $H^\star$ as function of vector x (no need to further be specified) and the initial SR-1 approximation $H$ are globally bounded in some norm of your choice by some real ...
- 21
0
votes
0
answers
43
views
Computing eigenvalues of a rank 1 matrix
For a fixed vector $\boldsymbol{v}\in\mathbb{R}^d$, I have the matrix $M=\boldsymbol{v}\boldsymbol{v}^\top$, from which I need to recover $\boldsymbol{v}$ (up to sign). I know that $\boldsymbol{v}$ is ...
- 53
0
votes
1
answer
42
views
Verify Sherman–Morrison–Woodbury rank-one update inverse
Given $A \in \mathbb{R}^{n \times n}$ non-singular and $a,b \in \mathbb{R}^n$, let $\overline{A} = A + ab^T$. If $\overline{A}$ is nonsingular then show that:
\begin{gather*}
\overline{A}^{-1} = A^{...
- 2,833
0
votes
2
answers
65
views
How to quickly tell this matrix is not rank 1?
Is it possible to quickly evaluate the following matrix is rank 1 or not?
\begin{pmatrix}
1 & -1 & -1 & 1 & 1 & 1 & -1 & -1 \\
-1 & 1 & -1 & -1 & 1 &...
- 1,062
1
vote
1
answer
97
views
Why is $xx'$ singular but ${\Bbb E}[xx']$ not (necessarily)?
Assume $x$ are random vectors and $x'$ denotes the transpose of vector $x$. In Hansen's Econometrics an assumption of the Linear Predictor model is that ${\Bbb E} [xx']$ is positive definite.
I get ...
- 185
0
votes
0
answers
65
views
Characteristic polynomial of convex combination
Given the following lemma on rank-$1$ matrices which I think I understand
How could I deduce the following on the characteristic polynomial of $A_s$? I don't get it just using multilinearity of ...
- 5,204
2
votes
3
answers
152
views
Let A be a complex $n \times n$ matrix with rank(A) = 1. Why is the minimal polynomial $x(x-Tr(A))$? [duplicate]
We know $rank(A) = 1$ so I have $n-1$ eigenvalues which are $0$
So my characteristic polynomial is $(x-0)^{n-1}(x-a) = x^{n-1}(x-a)$ with $a$ the last eigenvalue to determine.
Now, I found on some ...
- 49
1
vote
0
answers
78
views
Trace of square of a rank-$1$ Hermitian matrix ${\bf A} = {\bf a}{\bf a}^H$
Given matrix ${\bf A} = {\bf a}{\bf a}^H$, where ${\bf a}$ is a complex column vector. Are the following correct?
${\rm Tr}({\bf A}) = {\rm Tr} \left( {\bf a}{\bf a}^H \right) = {\rm Tr}({\bf a}^H{\...
- 162
0
votes
0
answers
42
views
Equivalence between first-order optimality conditions for rank-$1$ constraint and quadratic form
When simplified down, my optimization problem has the following structure
$$\underset{x\in\mathbb{R}^n}{\arg\min} \quad \left\| b - A\operatorname{vec} \left( x x^\top \right) \right\|_2^2$$
I am ...
- 81
0
votes
1
answer
74
views
Construct biorthogonal basis for rank-1 matrix? [closed]
Consider a rank-1 matrix $\mathbf{A}=\lambda\mathbf{u}\cdot\mathbf{v}^\mathsf{T}$ where $\lambda,\mathbf{u},\mathbf{v}$ are known. Let $\mathbf{A}$ be of size $N\times N$.
(Edit: A direct consequence ...
- 157
0
votes
2
answers
168
views
Prove that there is a rank one matrix $B$ so that $Bx = y$ where $B$ has matrix norm $1$
Let $\lVert \cdot \rVert$ denote a norm on $\mathbb{C}^m$. Define the dual norm $\lVert \cdot \rVert '$ by $\lVert x\rVert' := \sup_{\lVert y\rVert = 1} |y^* x|,$ where $y^*$ is the conjugate ...
- 479
-1
votes
1
answer
81
views
On the linear system $A x = 0$ when $A$ is rank-one
From Strang's textbook:
For rank-one matrices, we have that $u(v^Tx)=0 \implies v^Tx=0$. Why does this follow?
1
vote
1
answer
131
views
Connection between rank one matrices and rank one functions
Let $X$ be a finite set and $\mathbb{F}$ be a field. We say that a function
$f: X\times X \to \mathbb{F}$ is rank one if $f$ is of the form $(x,y) \mapsto a(x)b(y)$ for $a,b: X \to \mathbb{F}$. (See ...
- 413
0
votes
0
answers
231
views
Frobenius and spectral norms of rank-$1$ matrices
How to prove that $$\left\lVert x y^{\ast}\right\rVert_F = \left\lVert x y^{\ast}\right\rVert_2 = \left\lVert x\right\rVert_2 \left\lVert y\right\rVert_2$$ where $\forall x, y \in \mathbb{C}^n$?
I ...
- 147
3
votes
2
answers
183
views
Loewner order and rank-$1$ matrices
The Loewner order is defined over the set of Hermitian matrices as $A \leq B$ if and only if $B - A$ is positive semidefinite. If $B$ is a rank-$1$, positive semidefinite matrix, what are the matrices ...
- 233
1
vote
4
answers
455
views
Why is the matrix $x y^T$ rank one? [duplicate]
I am reading the definition of almost diagonal matrix:
DEFINITION. A matrix $A$ is almost diagonal (a.d.) if there exist a diagonal matrix $D$ and vectors $x$ and $y$ such that $$A=D+xy^T$$ That is, $...
- 1,062
0
votes
0
answers
287
views
Explaining the non convexity of rank 1 matrix
I understand from this post:
How can we show/prove that a rank-$1$ matrix is non-convex?
that a rank-1 matrix is non convex but I don't understand the proof. I know that the summation of two convex ...
0
votes
1
answer
100
views
Is this rank-$1$ (complex) matrix positive semidefinite?
In Is this rank-$1$ matrix semidefinite?, I have seen that $X = xx^T$ is PSD when $x$ is real. What about the case when $X$ is Hermitian?
I know that it is PSD but I'm not exactly sure how to prove it....
0
votes
0
answers
112
views
What does "rank one" in "rank one constraint system" mean?
Although rank one constraint system (r1cs) is heavily used in zero-knowledge proofs, I didn't find anywhere details on where the rank comes from.
- 147
1
vote
2
answers
331
views
Can this $3 \times 3$ tridiagonal Toeplitz matrix be rank-$1$?
I am trying to determine whether the following tridiagonal $3 \times 3$ matrix can have a rank of $1$.
$$\begin{bmatrix}a&b&0\\b&a&b\\0&b&a\end{bmatrix}$$
For $a = b = 0$, the ...
user1003610
0
votes
2
answers
444
views
$3 \times3$ matrices with rank $1$ or $2$ are manifolds
Let $M, N \subset \mathbb{R}^{n}$ be sets of matrices $3 \times 3$ with rank $1$ and $2$, respectively. Show that $M$ and $N$ are manifolds such that dim $M=5$ and dim $N=8$.
I have thought about ...
2
votes
1
answer
286
views
Find out the convex hull of the set $\left\{\pm \mathbf{u} \mathbf{u}^{T} \mid\|\mathbf{u}\|=1\right\}$ in a compact form ($u$ is a n-d vector)
According to the answer from @Cloudscape
The first step of finding the convex hull of a given set would be to visualize the convex hull and guess it.
The second step would be to prove your guess ...
- 23
2
votes
2
answers
1k
views
$2$-norm of a rank-$1$ matrix
I want to prove that $\|A\|_2 = \|x\|_2\|y\|_2$ given that $A = xy^T$ is a rank one matrix. This is my incomplete attempt so far, I get stuck when I need to take into account the spectral radius of ...
- 111
1
vote
4
answers
223
views
Given rank-$1$ matrix $A$, how to compute $A^{100}$?
$$A = \begin{bmatrix} 6 & 4\\ -6 & -4\end{bmatrix}$$ Find $A^{100}$.
I tried to find it using diagonalization, but as it is a singular matrix so one of eigenvectors came out zero. How $A^{100}...
7
votes
0
answers
1k
views
Convex hull of rank-$1$ matrices is the nuclear norm unit ball
Let
$$A := \left\{ u v^T : u \in \mathbb{R}^m, v \in \mathbb{R}^n, \|u\|_2 = \|v\|_2 = 1 \right\}$$
I would like to show that
$$\textrm{conv}(A) = B_* := \left\{ X \in \mathbb{R}^{m \times n}: \|X\|_* ...
- 325
3
votes
1
answer
452
views
Find a linear combination of matrices that has rank 1
Consider several linearly independent matrices $A_k \in \mathbb R^{m \times n}$ and the following equation
$$
\operatorname{rank} \left(A_0 + \sum_{k=1}^r c_k A_k\right) = 1.
$$
Here $A_k$ are fixed, $...
- 7,623
6
votes
4
answers
2k
views
$\det(I+A)=1+\operatorname{Tr}(A)$ if $\operatorname{rank}(A)=1$
Let $A$ be a complex matrix of rank $1$. Show that $$\det (I+A) = 1 + \operatorname{Tr}(A)$$ where $\det(X)$ denotes the determinant of $X$ and $\operatorname{Tr}(X)$ denotes the trace of $X$.
Any ...
user598858
2
votes
1
answer
476
views
$\lambda_{\min}$ and $\lambda_{\max}$ of rank-1 sum of matrices
It is explained from previous posts1,2 that for a rank-$1$ matrix $x_ix_i^T$ we have $\lambda_{\max} (x_ix_i^T)=1$ and $\lambda_{\min} (x_ix_i^T)=0$ with single and $N-1$ algebraic multiplicity, ...
- 823
0
votes
1
answer
54
views
Rank-1 matrix with two dependent rows?
I want to know what could be the possible rank of a matrix, which is constructed from a same vector but have two repeating rows.
Lets say I have a vector $$x=\begin{bmatrix}1 &a &1& b\end{...
-2
votes
1
answer
189
views
Number of rank 1 matrices with $0/1$ entries?
How many rank $1$ matrices in $\mathbb Z^{m\times n}$ are there if entries are restricted to $\{0,1\}$?
- 6,273
2
votes
1
answer
260
views
Finding rank-$1$ matrix
Let $$S = \frac{1}{12} \begin{pmatrix} 1 & 10 & 1 \\ 5 & 2 & 5\\ 1 & 2 & 9\end{pmatrix}$$ Find a rank-$1$ matrix $R$ so that $$ M = S + R $$ will have the same eigenvalues as $...
- 173
4
votes
1
answer
67
views
Minimal "dominating" rank-$1$ matrix
Given a matrix ${\bf A} \in \Bbb R^{n \times n}$, I would like to find a minimal rank-$1$ matrix ${\bf B} \in \Bbb R^{n \times n}$ such that the Frobenius norm of $ \| {\bf A} - {\bf B} \|_{\text{F}}...
- 579
3
votes
1
answer
21k
views
Finding the best rank-one approximation of the matrix $\bf A$
I have computed the singular value decomposition (SVD) of the following matrix $A$.
$$ {\bf A} := \begin{bmatrix}1&2\\0&1\\-1&0\\\end{bmatrix} = \underbrace{\left[\begin{matrix}0 & \...
- 1,400
0
votes
1
answer
925
views
How can we show/prove that a rank-$1$ matrix is non-convex?
In my optimization problem, I have a matrix $X = v v^H$ where $H$ denotes the complex conjugate transpose and $v \in \mathbb C^n$. This is a rank-$1$ matrix. In the published literature, it is ...
4
votes
4
answers
4k
views
Find the eigenvalues and eigenvectors of the matrix $A = uu^t$, where $u\in\mathbb{R}^n$
Find the eigenvalues and eigenvectors of the matrix $A = uu^t$, where
$u\in\mathbb{R}^n$
The multiplication will give me a $n \times n$ matrix like this:
$$\begin{bmatrix}
u_1^2 & u_1 u_2 &...
- 6,454
4
votes
3
answers
5k
views
Rank one orthogonal projector matrix.
My text is covering projector matrices while building up to Householder triangularization. The main topic of discussion is orthogonal projector matrices that satisfy
\begin{align} P &= P^2 \...
- 4,360
4
votes
1
answer
7k
views
Frobenius and operator norms of rank 1 matrices
$\newcommand{\opnorm}[1]{\left\| #1 \right\|_{\mathrm{op}}}
\newcommand{\norm}[1]{\left\| #1 \right\|}$
Suppose we have $X = x_1 x_2^\top \in \mathbb{R}^{n \times d}$ a rank-1 matrix which is non-...
- 4,025
1
vote
1
answer
586
views
Hessian with rank one
Let $\boldsymbol{\mathsf{H}}$ be the Hessian of the function $F(\boldsymbol{x})$. If this function is of the form
$$
F(\boldsymbol{x}) = f(\hat{\boldsymbol{\omega}}\cdot\boldsymbol{x})
$$
with some ...
- 314
1
vote
3
answers
1k
views
Does $\det(I+A) = 1 + \mbox{tr}(A)$ hold if $A$ is a rank-$1$ complex matrix? [duplicate]
If $A$ is a complex $n \times n$ matrix of rank $1$, then $$\det(I+A) = 1 + \mbox{tr}(A)$$
How to approach this problem?
Rank-$1$ matrices have special properties. Also, thinking about the ...
- 5,102
1
vote
1
answer
2k
views
All rank-1 matrices have an SVD
I have a rank-$1$ matrix $A \in \mathbb{R}^{m \times n}$ and a vector $u$ in its image. I could prove that the columns of $A$ are multiples of a vector $u$, and that $A$ can be written as $A = \alpha ...
- 13
6
votes
4
answers
407
views
How can I solve "average" best rank-$1$ approximation?
Assume I want to minimise this
$$ \min_{x,y} \left\| A - x y^T \right\|_{\text{F}}^2$$
then I am finding best rank-$1$ approximation of $A$ in the squared-error sense and this can be done via the SVD, ...
- 397
0
votes
3
answers
704
views
Approximating a given matrix with a rank 1 matrix Hadamard product with another given matrix
Let $A,B\in\mathbb{R}^{m\times n}$ be matrices with all positive entries. I want to compute the following minimum.
$$\min_{\vec{u}\in\mathbb{R}^m,\ \ \vec{v}\in\mathbb{R}^n} \ \ \sum_{i=1}^m \sum_{j=1}...
- 75
1
vote
3
answers
591
views
Factoring a given rank-$1$ matrix
Suppose you have a $n \times 1$ column vector
$$a=\begin{bmatrix}a_1\\{a_2}\\ \vdots\\{a_n}\end{bmatrix}$$
and a $1 \times m$ row vector
$$\quad b=\begin{bmatrix}b_1 & b_2 & \ldots & ...
- 131
4
votes
2
answers
543
views
Recover vector $x$ from rank-$1$ matrix $Q=xx^H$
Let the matrix $Q \in\mathbb{C}^{n \times n}$ be known. It is also known that $Q=xx^H$, where $x=[x_1,\ldots,x_n]^T$ and $x^H$ is its conjugate transpose. What is $x$? How to recover it?
- 395
1
vote
1
answer
521
views
Element-wise upper bound by rank-1 matrix
I would like to solve the following optimization problem for vectors $\mathbf{u} \in \mathbb{R}^m$ and $\mathbf{v} \in \mathbb{R}^n$, given a matrix $\mathbf{h} \in \mathbb{R}_{\geq 0}^{m \times n}$ ...
- 158
2
votes
1
answer
125
views
Applications where rank-1 matrices are useful
I am trying to list down applications where having a rank-1 matrix is advantageous. I know only of 2D convolution which boils down to a series of 1D convolutions if filter response is separable.
Can ...
- 1,013