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

learn more… | top users | synonyms

1
vote
1answer
36 views

How to recover Q from the (tiled) QR decomposition using householder factorisation?

I'm trying to implement the tiled QR decomposition in MATLAB (in an attempt to understand it), and I'm trying to check that my SGEQRF (upper corner tiles) function is working correctly. I have a ...
0
votes
0answers
40 views

How to find a transformation matrix T?

(1.) Suppose there is matrix C of dimension "p by n" where p is less then n i.e. p I want to know is there any particular way exist to find transformation matrix T of dimension "n by n" such that ...
0
votes
2answers
37 views

Eigenvalues and eigenvectors of a matrix

We know that if $\lambda (\neq 0)$ is an eigenvalue of a matrix $A$ corresponding to eigenvector $X$, then $\dfrac{1}{\lambda}$ is an eigenvalue of $A^{-1}$. But whether the corresponding eigenvector ...
0
votes
0answers
26 views

Orthogonal polynomials induction proof

I tried writing this all out but cannot seem to get anything sensible. Basically I want to prove that assuming w(x) is the weight function of a Gram Schmidt orthogonalization process and w is an ...
2
votes
1answer
89 views

Matrix Norm Inequalities and Linear Least Squares

I am working through one of my universities old QUALS and came across the following problem: Let $A,E\in \mathbb{C}^{m\times m}$. Suppose that $\sigma_\min>0$ is the smallest singular value of ...
0
votes
2answers
48 views

Is this Gram-Scmidt (or an application of) it?

I am given a $2\times 2$ matrix $$\left[ \begin{array}{ccc} a & 0 \\ 0 & b \\ \end{array} \right] $$ where $a,b \in \mathbb{R}$. I was told than an orthnormal basis for the colums of this ...
0
votes
1answer
80 views

Matrix with constant row sum

It is well known (and shown several times on this site) that if we have a matrix so that each row sums to zero then the matrix must be singular. I am curious if the following partial converse is ...
3
votes
1answer
127 views

Prove $|\det A| \leq \prod_{j=1}^n ||a_j||$

Let's say A is a square n by n matrix. ||$x$||=$x^T x$ and x is a real n-column norm. How would you show this? I tried to use the QR factorization here in showing that ||$a_j$||=||$r_j$||, but ...
1
vote
1answer
23 views

Question regarding Givens Rotation

I need to solve the following equation using Givens Rotation: $$ A\cdot x = b $$ Correction: I need to solve: $$ ||A\cdot x - b || \to \min $$ with $$A = \begin{bmatrix} 1 & 1 \\ -2 & ...
1
vote
2answers
135 views

Trace minimization of a matrix

Suppose $S = \pmatrix{1&1\\ 1&0\\ 0&1}$, $W$ is a $3\times3$ covariance matrix, which could be regarded as fixed. I need to find a $2\times 3$ matrix $Q$ that minimizes $$ ...
3
votes
1answer
217 views

Numerical verification of solution.

I have the non-linear equation \begin{align} &\left( {x}^{2}-1 \right) \left( -\frac{1}{4}\left({\frac { \left( 4\,{x}^{3}+2\, ex \right) ^{2}}{ \left( {x}^{4}+e{x}^{2}+f \right) ...
2
votes
2answers
59 views

How to figure out the spectral radius of this matrix

$$A=\begin{array}{ccc} 0 & 1/2 & 0 & \cdots & 0 \\ 1/2 & 0 & 1/2 &\cdots& 0\\ 0 & 1/2 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots &\ddots ...
1
vote
0answers
56 views

Numerical algorithm to solve quadratic eigenvalue problem.

Given the equation $$-4 \left(a^2+a (n-1) (2 t^2-1)\right) \left(\sum _{i=0}^n \alpha_i t^{2 i}\right)^2 \\ +\frac12 \left(\sum _{i=0}^n \alpha_i t^{2 i}\right) \left(t \left(8 a (t^2-1)+1\right) \sum ...
0
votes
1answer
52 views

Avoiding gimbal lock

I am not really sure if I understand the phenomenon of gimbal lock correctly. Say I have a vector $\begin{pmatrix} x\\ y\\ z \end{pmatrix}$. And I want to keep the vector's length fixed but move it ...
1
vote
1answer
127 views

Norm of Block Diagonal Matrix

Given a matrix $A \in R^{m \times n}$ with known upper bound on the operatornorm $\| A \|$ I want to find an upper bound for the operator norm of the square root of the following matrix that is given ...
7
votes
1answer
231 views

Fast algorithm for approximating Eigenvalue distribution of large sparse matrix

I am interested in the eigenvalue distribution of a huge $2^{16}$x$2^{16}$ Hermitian sparse matrix with spectrum contained in $[-1,1]$. That is I don't need to know all eigenvalues exactly, but rather ...
1
vote
1answer
71 views

Proof that eigenvector corresponding to simple eigenvalue is continuous

Let $\lambda$ be a simple eigenvalue of $A \in L(C^n)$ and let $x$ be the corresponding eigenvector. Then for $E \in L(C^n)$, $A+E$ has an eigenvalue $\lambda(E)$ and an eigenvector $x(E)$ such that ...
1
vote
1answer
25 views

linear systems&normalize

suppose $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ be a linear function which can be represented by a $n \times n$ matrix. Then the jacobian of $f$ is the same as the function for $f$. But I now want ...
0
votes
0answers
41 views

Kalman Filter Predict Update of LDL Decomposition of a Covariance Matrix

From the state predict equation: http://en.wikipedia.org/wiki/Kalman_filter# $$P_{n+1}=AP_nA^T + Q$$ Suppose the $LDL^{T}$ ( http://en.wikipedia.org/wiki/Cholesky_decomposition#LDL_decomposition_2 ) ...
1
vote
0answers
22 views

Algorithm for finding only the $k$-th singular vectors

I know that we have truncated SVD that can compute the first say $k$ largest singular values (and corresponding singular vectors). However, I'd like to know if there is an algorithm that can find only ...
1
vote
0answers
45 views

Best way to solve specific block-tridiagonal linear system (10000x10000 and larger)

To provide more context, this system came from energy balance equation on a mesh with (n,m) nodes in each direction. It's a linear system that looks like this (size of system in blocks n = 4, size of ...
0
votes
1answer
51 views

Induced Matrix Norm

I have trouble following a proof of the induced Norm $||\cdot||_1$ The proof can be found here: ...
0
votes
0answers
19 views

Maximal angle between kernel of rows of a matrix

Consider a matrix with 2 columns $$ \begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \\ a_3 & b_3 \\ \vdots & \vdots \end{pmatrix} . $$ To each row $(a_i \;\;\; b_i)$, one draws the kernel ...
2
votes
1answer
129 views

Check if the following gradient is correct

This question regards the verification of the gradient of a given function. Notation. Let $N, K \in \mathbb{N}_0$ be given (nonzero) integers, with $K > N$. Let $\mathbf{x} = [x_b \ y_b \ z_b]^T ...
0
votes
1answer
24 views

How to evaluate the accuracy for sparse linear system solver

I'm currently trying to do some experiments on linear solver. However, it's a little hard to get the sense of the numbers. For example, I know large condition number is bad, but how large is bad? ...
2
votes
1answer
63 views

Least squares problem with orthonormality constraints

Given $y_1,\ldots,y_n\in \mathbb{R}$,$w\in \mathbb{R}^d$, and $x_1,\ldots x_n\in \mathbb{R}^D$, how do we solve the following optimization problem \begin{align} \min_A \sum_{i=1}^n (y_i-w^TA^Tx_i)^2\\ ...
2
votes
1answer
274 views

equations solved with Newton's method by finding the zeros of functions?

I found this statement in one paper I read recently: This problem can be solved by finding the zero of functions: ...
0
votes
0answers
28 views

Not enough memory for GMRES

After realizing that Gauss-Seidel is extremely slow for my simulation, i wanted to try GMRES and luckily found the C++ code here without diving into the theory. The size of the matrix in my case is ...
1
vote
1answer
41 views

QR decomposition error

How to find $$||A - QR||_2$$ without finding Q matrix (A is matrix, QR - qr decomposition of A) I have written a code which return only R (using Householder transformation).
1
vote
2answers
394 views

Gauss-Seidel method convergence algorithm

From Wikipedia: The convergence properties of the Gauss–Seidel method are dependent on the matrix A. Namely, the procedure is known to converge if either: ...
2
votes
1answer
126 views

Finding vector $x$ so that $Ax=b$ using Householder reflections.

Assume $n\times m$ matrix $A$ and vector $b$ are given. I am looking for $x$ that satisfies $Ax=b$ in terms of linear least squares problem. Let $A=\begin{bmatrix} 1 & 1 & 1 \\0 & 1 & ...
1
vote
1answer
281 views

block matrix multiplication

If $A,B$ are $2 \times 2$ matrices of real or complex numbers, then $$AB = \left[ \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right]\cdot \left[ \begin{array}{cc} b_{11} ...
1
vote
0answers
34 views

Solving a linear equation with a moderatly sparse 1000000*1000000 symmetric matrix

I've got a linear equation $A_{n*n}\cdot x=1_n$, where $n=1000000$ and $A$ is symmetric with approx $1000$ nonzero entries in each column and row. What would be the best numerically stable algorithm ...
2
votes
1answer
63 views

fast multiplication for a matrix and its transpose.

I know Strassen and other methods can achieve better than $O(n^3)$ for general square matrix multiplication. I am curious of the spacial case where the multiplication is between a $n*m$ matrix $A$ ...
1
vote
1answer
218 views

Proof that Newton Raphson method has quadratic convergence

I've googled this and I've seen different types of proofs but they all use notations that I don't understand. But first of all, I need to understand what quadratic convergence means, I read that it ...
3
votes
1answer
54 views

Spectral norm of symmetric matrices only with the diagonal, the first column, and the first row non-zero

Consider a real symmetric matrix $$\mathbf{M}=\left[\array{a_0&a_1&a_2&\cdots&a_n\\ a_1&b_1&0&\cdots&0\\ a_2&0& b_2&\cdots&0\\ \vdots &\vdots ...
0
votes
1answer
70 views

Is this matrix guaranteed to be positive-definite?

(This question pertains to a larger model proposed in this SIGRAPH paper, but I've pulled out the pertinent question and generalized it.) Let's say I have two large matrices $M$ and $L ...
0
votes
1answer
26 views

Matrices in Linear Algebra

Let: $ u: R^2 --> R^3$ be defined by: $$ u(x,y)=(x+2y, 2x-y, 2x+ 3y)$$ Give the matrix $M[u]$ in the canonical base of its definition space. This question might seem sort of stupid, but it was ...
0
votes
0answers
54 views

Francis Algorithm (Implicit QR Algorithm)

In Numerical Analysis, we are touching upon QR and Francis Algorithm. I understand that for Francis's Algorithm, we reduce the matrix to its upper Hessenberg form using Householder transform. What I ...
4
votes
1answer
235 views

9 point stencil for Laplacian operator

Given the following 9 point Laplacian \begin{align} -\nabla^2u_{i,j} = \frac{2}{3h^2}\left[5u_{i,j} - u_{i-1,j} - u_{i+1,j} - u_{i,j-1} - u_{i,j+1} - u_{i-1,j-1} - u_{i-1,j+1} - u_{i+1,j-1} - ...
1
vote
1answer
32 views

QR decomposition

Assuming that we have a QR decomposition of a matrix $A \in \mathbb{R}^{m \times n}$, $Q \in O(m)$ and $R \in \mathbb{R}^{m \times n}$ such that $A=QR$, where R is an upper triangular matrix. Now ...
5
votes
1answer
37 views

proving a theorem of alternative

I've read the following exercise in my book: Let $A\in\mathbb R^{m\times n},b\in\mathbb R^m,c\in\mathbb R^n$. Then exactly one holds: $Ax=0,c^t\cdot x=1$ with $x\geq0$ has a solution $A^ty\geq c$ ...
1
vote
1answer
179 views

Trapezoid Rule to Simpson's Rule Extrapolation

I need to show that one extrapolation of the trapezoid rule leads to Simpson's rule. I've looked through the other posts on ME, specifically the post with the same title, and this for help, but I ...
2
votes
1answer
104 views

(A + D)x = b … efficiently!

let say we have $A$ to be symmetric positive-definite (SPD), moreover block tridiagonal Toeplitz matrix and $D$ is block diagonal SPD (both with full rank). Let say we know everything about $A$ and ...
0
votes
1answer
34 views

Its about Finding the values of (A) for which the system has no solution, infinitely many solutions, and a unique solution in linear Algebra [duplicate]

I really couldn't find the answer no matter how i tried Plz Help when I tried to solve it i got a really big numbers like a^6 ..etc' Okay what I did with this question is solving it by reducing the ...
0
votes
0answers
51 views

Upper Hessenberg Form

I am given a matrix. I would like to reduce it to its upper Hessenberg Form. We are discussing eigenvalue computations in Numerical Analysis and the textbook just gives the algorithm for it without an ...
0
votes
2answers
17 views

Is there a formula for finding the series of numbers based on an average.

So I am working on a program that does a scrolling effect. the image is 1200pixels wide, and each time it scrolls, it should move an average of 2.67 pixels. However I am using a function that does not ...
2
votes
1answer
37 views

Vector optimization with set constraint

This is a more generalized form of a previous unanswered question, from which I've removed all the content that wasn't relevant to the actual problem. I have a minimization problem of the form $$ ...
3
votes
1answer
52 views

Linear Algebra quesion

$A^{-1} - \lambda A = B^{-1} - \lambda B - \alpha v v^T$ $A, B \in S^n_+$; $v \in R^n$; $\lambda, \alpha \in R_+$. Can we solve A in term of other variables?
3
votes
1answer
57 views

Necessary and Sufficient conditions for convergence of matrix iterations

I need some help figuring out how to go about the iteration part of the problem...I don't really know where to start. If someone can please help take me through it that would be greatly appreciated. ...