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

learn more… | top users | synonyms

1
vote
1answer
35 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
226 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
323 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
50 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
27 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
53 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
131 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
49 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 ...
1
vote
1answer
149 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
1answer
128 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
83 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
128 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
34 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
110 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
107 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
34 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
282 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
64 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
40 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
388 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
18 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 ...
-3
votes
1answer
72 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$? ...
1
vote
0answers
67 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
59 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
113 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
78 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
119 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
351 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
45 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 ...
0
votes
0answers
146 views

Symmetric Tridiagonal QR Algorithm

I have a question regarding QR algorithm. Suppose we are being given a symmetric tridiagonal matrix A (4X4) and perform QR factorization on A: A=QR. Then we define A':=RQ. A' still possesses the ...
1
vote
0answers
60 views

Reformulating objective function of canonical correlation analysis

Given two column vectors $X = (x_1, \dots, x_n)'$ and $Y = (y_1, \dots, y_m)'$ of random variables with finite second moments, canonical-correlation analysis seeks vectors $a$ and $b$ such that the ...
0
votes
1answer
63 views

Need Help! Recognizing types of errors: Truncation and Roundoff

I am a little unclear on the difference between the two. What exactly are they? As simplified as possible :) How can i recognize them and identify parts of formulas or algorithms that would give ...
2
votes
1answer
535 views

Why is the matrix norm $||A||_1$ maximum absolute column sum of the matrix.

By definition, we have: $||V||_p=\sqrt[p]{\displaystyle \sum_{i=1}^{n}|v_i|^p}$ $||A||_p=sup\frac{||Ax||_p}{||x||_p}$, $x\not=0$ and if $A$ is finite, we change sup to max. However I don't really ...
0
votes
1answer
50 views

how to find thet a given real symmetric matrix is positive definite, positive semidefinite, negative definite, negative semidefinite or indefinite.

How to find that a given real symmetric matrix is positive definite, positive semidefinite, negative definite, negative semidefinite or indefinite.; on the basis of principle diagonal minor.
0
votes
2answers
20 views

if $v$ is a member of $H$ and $v$ is not a member of $M$ then $u$ is member of $K$. How is this possible?

Let $(V,K)$ and $u,v$ is a member of $V$. Suppose that $M$ is a subset of $V$ is a subspace of $V$ with basis $B_m=\{m_1,...,m_r\}$ with $r$ less than and equal to $n$. Let $H$ be a subspace spanned ...
0
votes
1answer
110 views

Singular value decomposition: rotation

Suppose that $A \in \mathbb{C}^{m \times n}$ and $B$ ($ \in \mathbb{C}^{n \times m}$) is the matrix obtained by rotating $A$ ninety degrees clockwise. Do $A$ and $B$ have the same singular values? ...
3
votes
1answer
5k views

Distance/Similarity between two matrices

I'm in the process of writing an application which identifies the closest matrix from a set of square matrices $M$ to a given square matrix $A$. The closest can be defined as the most similar. I ...
1
vote
0answers
41 views

Matrix computing

Given an $n$-vector $x$, show that floating-point computation of the Householder vector $v$ such that $P x = (I − 2vv^{T} )x = \pm\left\|x\right\|_{2}e_{1} $ gives a forward stable result $v^{\prime}$ ...
0
votes
1answer
39 views

quick factorization of rank-one matrices (generally, and of a particular form)

Let $Q$ be an arbitrary non-zero matrix and let $x$ be a column vector. It should be true that $xx^TQ$ and $Qxx^T$ are both rank 1 matrices. It is a fact that all rank-one matrices can be factorized ...
1
vote
1answer
118 views

Bilinear Coons patches

Suppose that we have two bilinear Coons patches which share a common curve. Studying on Farin I find that, generally, these two surfaces join with C^0 continuity along that common curve, but I don't ...
0
votes
1answer
38 views

Time of point colliding with a moving line

In 2-D space, given a line defined by two points a and b, and a third point c that is not initially (t=0) in the line defined by a and b, is it possible to obtain an expression for the numerically ...
0
votes
2answers
1k views

Prove that the determinant of a householder matrix is -1

I understand that a householder matrix has eigenvalues of either 1 or -1, however I isn't clear to me why the determinant is -1. Clearly the determinant is equal to the product of the eigenvalues so ...
1
vote
0answers
115 views

Matrix-valued expansion in spherical harmonics

I am seeking a clever solution to the following problem. Given $$X(\theta,\phi) = exp(-iA(\theta,\phi))\; B\; exp(+iA(\theta,\phi))$$ with the square, Hermitian matrix $A$: $$A(\theta,\phi) = A_{0,0} ...
5
votes
1answer
239 views

Uniform sampling of points on a simplex

I have this problem: I'm trying to sample the relation $$ \sum_{i=1}^N x_i = 1 $$ in the domain where $x_i>0\ \forall i$. Right now I'm just extracting $N$ random numbers $u_i$ from a uniform ...
2
votes
1answer
553 views

What is the operation count for QR factorization using Householder transformations?

I have a hard time finding the operation count of QR factorization when using Householder transformations. The answer is $2mn^2 - \frac{2n^3}{3}$, but have no clue on how to get this count following ...
1
vote
3answers
85 views

How to solve this matrix using gauss-elimination by hand

I feel like i am having a brain fart. I have been given this $Ax=b$ system: $A= \begin{pmatrix} 0.913 & 0.659 \\ 0.780 & 0.563 \end{pmatrix}$ $b= \begin{pmatrix} 0.254 \\ 0.217 \end{pmatrix}$ ...
1
vote
1answer
71 views

Convergence of Recursive algorithms

In a kind of signal processing problem I faced the following recursive (boot-strap) algorithm: $$R_{k} = R_{k-1} + (y_k-H s_{k-1})*(y_k-H s_{k-1})^T$$ $$s_k = (H^T R_k^{-1} H)^{-1} H^T R_k^{-1} ...
1
vote
0answers
892 views

The spectral radius of the matrix $A$ is less than or equal any natural norm

Show that the spectral radius of the matrix A is less than or equal any natural norm, i.e: $$\rho(A) \leq ||A||=\max_{||x||=1}{||Ax||}$$ where $\rho(A)=\max\{|\lambda|:\lambda \text{ is a eigenvalue ...
2
votes
1answer
198 views

1D Schrodinger/Laplace equation via finite differences: incompatible eigenvalues

I need to solve a variant of the 1D Schrodinger's equation equation using finite differences, so I decided to play a little bit with the real-space representation of some operators. Using the ...