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

learn more… | top users | synonyms

1
vote
4answers
94 views

Proof $\langle Ax,y\rangle = \langle x,A^*y\rangle$ when $A$ Hermitian

I was trying to understand a proof of why a Hermitian $A$ matrix has its eigenvectors orthogonal. As part of the proof they state $$\langle Ax,y\rangle = \langle x,A^*y\rangle$$ From which property ...
1
vote
0answers
93 views

Solving linear system of equations using Successive Over-Relaxation

I was solving a system of linear equations with SOR. I used different values of relaxation factor (w) for the different runs. I found that for all w > w' (1 < w' < 2), the error is the result ...
1
vote
0answers
40 views

Orthogonal Procrustes Problem

The classical orthogonal Procrustes problem concerns finding the matrix $\Omega$ which minimizes $||A\Omega-B||_{F}$ subject to $\Omega'\Omega=I$, with A and B known matrices. Let A be the identity. I ...
0
votes
1answer
85 views

Solving Poisson Equation Finite-difference using maple

How do I solving Poisson Equation Finite-difference using maple consider Poisson equation $$\frac{\partial^2u}{\partial x^2} (x,y)+ \frac{\partial^2u}{\partial y^2} (x,y) = x*e^y$$ $0<x<2$ ...
4
votes
1answer
71 views

QR factorization of a special structured matrix

A friend asked me the following interesting question: Let $$A = \begin{bmatrix} R \\ \xi{\rm I} \end{bmatrix},$$ where $R \in \mathbb{R}^{n \times n}$ is an upper triangular and ${\rm ...
0
votes
0answers
75 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
70 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
45 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
43 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
168 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
72 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
103 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
76 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
67 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
68 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
174 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
59 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
216 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
103 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
50 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 ...