Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

0
votes
0answers
74 views

when fixed Point Iteration does not converge?

I want to solve a nonlinear system with the fixed point iteration method. I have initial condition,and the answer is known. By using this method the answer converges very slowly about 1000 iteration ...
0
votes
1answer
14 views

Are Similar Matrices and Unitary Property related?

Recall that 2 matrices $A, B\in R^{n,n}$ are similar if there exists a matrix $P$ such that $A=P^{-1}BP$. In this case is $P$ always orthogonal?
0
votes
1answer
45 views

Find upper Hessenberg by Householder transformation

I have a matrix that looks like this: $$ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \epsilon & 0 & 0 & 0 \\ ...
2
votes
1answer
49 views

Show that every operator norm is consistent

Is the following a correct way to show that operator norms are consistent? $$ \|AB\|=\max_{Bx \ne 0}\frac{\|ABx\|_\alpha }{\|x\|_\alpha} =\max_{ Bx\ne 0}\frac{\|ABx\|_\alpha}{\|Bx\|_\alpha} ...
3
votes
1answer
69 views

Computational cost, power method and page rank

When solving the PageRank problem for $n$ web pages, it is necessary to find a solution of the eigenvector equation $$(fM)*p = p,$$ where $$fM = dM + (1 - d)Z$$ $$Z =\frac{1}{n}*ee^T$$ $$e =[1, 1, ...
3
votes
2answers
69 views

Proof that $(\alpha I - A)$ invertible if $\alpha > \rho(A)$

I want to proof that for $A \in \mathbb{R}^{n \times n}$ with $a_{ij}\geq 0, \forall i,j=1,...,n$: \begin{align} (\alpha I - A) \text{ is invertible if } \alpha > \rho(A) \end{align} where ...
2
votes
1answer
67 views

Something about Gram-Schmidt Projections

Recently I'm reading the book Numerical Linear Algebra and I have a problem in Lecture 8, Gram-Schmidt Orthogonalization. The following text is from the book. Let $A\in\mathbb{C}^{m\times n}$, ...
0
votes
0answers
41 views

How to solve a divergent linear system using iterative methods?

I have a matrix A which is symmetric and non-diagonal dominant. I tried to use Jacobi/Gauss-Seidel/SOR to solve it but it diverges. Is there any mechanism to condition the matrix for convergence ...
2
votes
0answers
38 views

Finding generalized eigenvalues with linear constraints

I have a generalized eigenvalue problem $$Mx = \lambda Bx$$ with the additional constraint that $Cx=0$, where $M$ and $B$ are positive-definite and $C$ is a sparse and rectangular. Is there a simple ...
1
vote
0answers
44 views

$F(x)=Ax+b$ is a contraction mapping

I want to proof that $f(x)=Ax+b$ with \begin{align} A = \begin{bmatrix} 0 & -\frac{1}{8} & \frac{1}{4} \\ 0 & \frac{1}{3} & 0 \\ -\frac{1}{2} & -\frac{5}{22} & \frac{3}{4} ...
0
votes
1answer
45 views

Least Square with homogeneous solution!

I've read somewhere that: $x=A^+b+(I-A^+A)Z$ is a solution for $Ax=b$ ,when is doesn't have a particular solution. where $A^+$ indicates the pseudo-inverse and $Z$ is an arbitrary vector!!! I know ...
0
votes
1answer
28 views

Expressing a vector as the best linear combination of “random” vectors

Suppose I have something like: $\vec{v} = \langle 1, 2, 3, 4, 5 \rangle$ and I have a set of vectors (these are all just made up numbers): $\vec{w_1} = \langle 3, 7, -2, -4, 8 \rangle$ $\vec{w_2} ...
3
votes
2answers
90 views

Interesting determinant: Let $A$ be an $n$ by $n$ matrix with entries $a_{i,j}$ given that $a_{i,j}=2$ if $i=j$

Let $A$ be an $n$ by $n$ matrix with entries $a_{i,j}$ given that $a_{i,j}=2$ if $i=j$, $a_{i,j}=1$ if $i-j\equiv\pm2\pmod n$, and $a_{i,j}=0$ otherwise. Find $\det A$. It seems that the ...
1
vote
2answers
41 views

stability function

I have an exercise which asks me to find polynomials $P$ and $Q$ with a degree $2$ that satisfy $$\exp(z)= \dfrac{P(z)}{Q(z)} + O(z^5)\ \text{for} \ z\to 0$$ My question is: Are they actually unique ...
0
votes
0answers
42 views

Find nullspace from one removed column

I have a large, sparse, square matrix $B$ that is full rank, and am going to remove one column from it to get a new matrix $B_{red}$. I also have a matrix $S$ of candidate columns, one of which needs ...
0
votes
1answer
12 views

Question about flipping terms in matrix multiplication in proving that $h(N_n(\mu , K))=\frac{1}{2}\log(2 \pi n)^n |K|$

So in my book, it is written: Let $X_1,X_2,...,X_n$ have a multivariate normal distribution with mean $\mu$ and covariance matrix $K$ and $\textbf{X}=(X_1,X_2,...,X_n)$ The above isn't really ...
1
vote
1answer
33 views

numerical computation without explicitly calculating certain matrices

I have to numerically multiply: $A^{-1} B A$ where B is a diagonal square matrix, and A is symmetric. A is calculated from multiplying two non-square matrices, $A = XX^T$ I know B and X, and A and ...
8
votes
2answers
179 views

Advice in Bachelor Degree

First of all, I´m very sorry for my bad english, especially writing. Ok, for differents problems i´m studing a Bachelor degree in Mathematics. These degree is online. Now, the problem with my school ...
1
vote
1answer
163 views

Jordan Canonical form 2x2 matrix

Compute the Jordan Canonical form of A = $\begin{bmatrix}i & 1\\1 & -1\end{bmatrix}$. My (feeble) attempt: After I compute the characteristic polynomial, which gives me $x^2=0$, the ...
2
votes
0answers
22 views

Nontrivial Matrix-estimate

I try to proof the following estimate: \begin{align} h' W^{-1} H W^{-1} h \geq c h' H h \qquad c>0, \qquad\qquad (1) \end{align} where $h\in\mathbb{R}^{K-1}$ and ...
0
votes
1answer
42 views

Combine 2 sparse QR factorizations

I have sparse matrix $A_1$ which is size $m_1 \times n$ and another sparse matrix $A_2$ which is size $m_2 \times n$, where $m_1 < n$ and $m_2 \leq n$ and plan on stacking them to make a sparse ...
0
votes
1answer
26 views

Set up for matrix solutions

I've haven't touched linear algebra in a while so I'm sorry if this seems simple but I did a google search and I am still confused. I have to find a solution to the following set of equations: ...
1
vote
1answer
24 views

$l_1$ Matrix Norm Inequality

I am independently studying Numerical Analysis and came upon the following question: $l_1$ vector norm $||x_1||$ is defined as $||x_1||=\sum|x_i|$. How can we show that for the natural matrix ...
1
vote
1answer
69 views

Richardson Iteration

Given the Richardson Iteration, $x_{n+1} = x_n + \alpha(b-Ax_n)$ (with $\alpha$ a scalar constant). To which polynomial $p(A)$ at step $n$ does this iteration correspond to? My first idea ...
0
votes
1answer
40 views

Generalized minimal residuals: eigenvalues and sets of functions

Can someone help me on this exercise (2 parts)? Thanks! Suppose that $S \subseteq \mathbb{C}$ is a set whose convex hull contains $0$ in it's interior (so $S$ is contained in no half-plane ...
0
votes
1answer
101 views

Numerical range of a matrix contains the convex hull of the eigenvalues.

I am stuck with the following question. Question: Let $A \in \mathbb{C}^{m \times m}$ be arbitrary. Let $W(A)$ be the numerical range i.e. the set of all Rayleigh quotients of $A$ corresponding to a ...
0
votes
0answers
29 views

code to factorize block toeplitz matrix fast and stable

My goal is to factorize (LU or QR) a symmetric, semi-positive block Toeplitz matrix as quickly and as stably as possible. A classic fast algorithm, for example, is the Levinson algo, but it is rather ...
0
votes
1answer
74 views

On eigenvalues, hermitian matrices and SVD

Are my ideas on the following "true or false"-statements correct? If $A$ is hermitian and $\lambda$ is an eigenvalue of $A$, then $|\lambda|$ is a singular value of $A$. My answer would be ...
1
vote
0answers
66 views

Applications of Numerical methods

I'm in a course of Numerical Methods and part of an assignment is find an article about an application of numerical methods, explain this article and present a program (in matlab/octave) that ...
0
votes
1answer
64 views

Backward stable algorithm

Assume we have fixed unitary matrices $Q_1, \dots, Q_k \in \mathbb{C}^{m,m}$ and a matrix $A \in \mathbb{C}^{m,n}$ which can be perturbed. How can we proof that the algorithm on computing the product ...
0
votes
1answer
25 views

Avoid evaluation of a very large matrix in non-negative matrix factorization

This is somewhere in between a math and a programming question, so please send me back to SO if you think it's off-topic. I'm implementing non-negative sparse coding, a regularized variant of ...
2
votes
0answers
61 views

Inverse of Sum of Matrix Inverses

Given $N$ positive-definite matrices $\Lambda_i$, I need to efficiently compute $\Gamma_N$, where $$ \Gamma_n = \left(\sum_{i=1}^n \Lambda_i^{-1}\right)^{-1}. $$ Applying the Woodbury matrix identity ...
0
votes
2answers
66 views

Range and kernel of a linear transformation are ALWAYS disjoint

Is it true that the Range and kernel of a linear transformation are ALWAYS disjoint. I think they are not but I remember in my notes that the ker L= Im (L') this was under projections. So I am unsure ...
0
votes
1answer
33 views

What does left composition mean in this question?

Consider the vector space of all linear transformations $L(V,V)$ on the vector space $(V,K)$ and a linear map $F:L(V,V)\to L(V,V)$ such that $F(a)= b \circ a$ for all $a\in L(V,V)$, where $b\in ...
0
votes
1answer
173 views

If $(V,k)$ is a finite-dimensional vector space, then the space of all linear transformations on $V$ is finite dim and find its dim?

My issue with this is the only way I know how to prove it is to set $\dim V=n$, but then that wouldn't make sense because the second part is find the $\dim$. What I was thinking is using the ...
2
votes
1answer
58 views

Verify the spectral radius $r(A) = \lim_{n\rightarrow\infty}||A^n||^{1/n}$.

I want to Verify the spectral radius $r(A) = \lim_{n\rightarrow\infty}||A^n||^{1/n}$. Where $A$ is a matrix. I have a proof that involves Jordan Blocks. The proof is long and involved but it not ...
1
vote
1answer
35 views

an estimate for condition number: $\kappa(C^{-1}A)\leq \kappa(C^{-1}B)\kappa(B^{-1}A)$

I'm currently reading through "Domain Decomposition Methods" by Tosseli and Widlund and in the appendix I found the following Theorem: Let A, B, C be symmetric positive definite matrices. Let ...
1
vote
1answer
212 views

Natural Cubic Spline 3 points

I am trying to do a natural cubic spline but I'm having trouble. f(-.0247500)=-.5, f(.3349375)=-.25, f(1.101000)=0 I tried doing the matrix, Ax=b where, h0=h1=.25 an a0=-.0247500, a1=.3349375, ...
0
votes
1answer
16 views

Stability and complexity of some functions

Can someone check if my solutions/arguments on this exercise are correct? Thanks! Are the following statements true or false? $\sin (x)=\mathcal{O}(1)$ as $x \rightarrow \infty$ $\sin ...
0
votes
0answers
102 views

Row & Column Removal and Rank Reduction

I have a problem involving a n x n square, real matrix $K$ which is initially full rank and is not positive definite. In each iteration of my program, I have to remove a row and the corresponding ...
-3
votes
1answer
55 views

Conditional number: exercise

Let's say we've got a $202 \times 202$ matrix $A$ for which $||A||_2=100$ and $||A||_F=101$ (the Frobenius norm). How can we find the sharpest bound (lower) on the 2-norm condition number of $A$? ...
0
votes
0answers
23 views

Calculating a 3d vector based on two functions based on time

I have an object who's position is defined by a 3d vector, startposition. I want to translate this object towards another position, endposition. At the same time, I also want to translate this ...
0
votes
0answers
33 views

How to generate random matrices when it's singular values are given?

Consider matrix S as nxn diagonal matrix with singular values populated across the diagonals in non-increasing order. I want to know how to create random matrix A whose singular values with be the ...
1
vote
0answers
49 views

How to condense a matrix to a vector

I'm not an experienced person in mathematics and this might either sound like a trivial question or a stupid one. However, this problem arose to me when I was writing a program. Following is my ...
3
votes
1answer
54 views

Proving an identity

We define $\|x\|_A^2:= x^TAx$ and $(x,y)_M := y^TMx$ for a symmetric positive definite matrix $A$ and an invertible matrix $M$. I want to show the following identity for the errors of Richardson's ...
2
votes
0answers
89 views

How to generate a random matrix which have given singular values?

I know one method: generate a random matrix, apply SVD decomposition, modify singular values, and then multiply those matrices back together. However, I'm wondering how random this method is. Since ...
2
votes
1answer
74 views

Characterizing a matrix with identical eigenvalues

Suppose $n \times n$ hermitian and positive semi-definite matrix $A$ is given. We can rewrite $A$ using its eigen decomposition, $$ A = U_A \Lambda_A U_A^H. $$ Now suppose matrix $B$ is also $n ...
1
vote
1answer
91 views

Preservation of Positive-Definiteness from Small Perturbations

Let $A$ with real positive entries be a Hermitian positive definite matrix. I'm wondering if one perturbs $A$, e.g., $\hat{A}=A+\Delta A$, would the matrix still be positive definite? I'm told this is ...
3
votes
1answer
193 views

What are non-orthogonal eigenvectors?

Given a symmetric matrix $A$, the maximum of the trace, $Tr(Z^TAZ)$ under the assumption that $Z^TZ=I$ occurs when $Z$ has the eigenvectors of $A$, as $Tr(U^TAU)= \lambda_1 +\lambda_2+...\lambda_ d$ ...
0
votes
1answer
31 views

Constrained non-linear optimisation algorithm making use of problem structure

I have a problem that in some ways is quite simple and in other ways is quite hard. I feel that there is probably an algorithm out there that is better suited to solving my problem than the one I am ...