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

learn more… | top users | synonyms

1
vote
2answers
59 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: ...
1
vote
2answers
63 views

eigenvalues for symmetric and non-symmetric matrices

I know the Power methods and Jacobi methods are suitable to finding eigenvalues for symmetric matrices, please tell me other methods for this matrices. And what are the methods for the Non-symmetric ...
3
votes
1answer
215 views

How to Store a Banded Matrix by Diagonal

I'm taking a graduate level independent study course this semester in Matrix Computations. I'm not getting much support from the professor, so am turning to the excellent StackExchange community for ...
2
votes
1answer
47 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
48 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$ ...
2
votes
1answer
118 views

A Beautiful Determinant!

Find the determinant of the following matrix in the terms of $a_1,a_2,\cdots,a_n$ explicitly, $$ \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_n\\ a_2 & a_3 & a_4 & \cdots ...
2
votes
1answer
82 views

SOR and Gauss-Seidel Method - Confusion

Can anyone explain to me the SOR Method for finding the root(s) of a function? Its supposedly very similar to the Gauss-Seidel method. The Gauss-Seidel method, from my understanding, is similar to ...
2
votes
1answer
60 views

Numerical methods for inverting non positive definite matrices

I'm working on a PDE solver and need to invert the following matrix written in block form $\left( \begin{array}{cc} kM & -S \\ -S & M \end{array}\right) $ where M and S are the usual mass and ...
2
votes
1answer
135 views

Question on “avoidance of crossing”

In review of linear algebra I come across this phenomenon, the Google Book link is this: What I do not understand is Lax tried to persuade us that "there is another way of parametrizing these ...
1
vote
1answer
28 views

Lipschitz continuity for generalized inverse matrix

Suppose $A$ and $B$ are full-rank and well-conditioned. Is Lipschitz continuity held for generalized inverse? $$\|A^+ - B^+\| \le \omega \|A-B\|,$$ for some $\omega > 0$, where the norm could ...
1
vote
1answer
40 views

Can a tridiagonal matrix be rectangular?

My program works with tridiagonal matrices (calculates its LU decomposition) so before doing anythig, it stores the matrix in 3 vectors: the three diagonals only. So far my conclusion was, a ...
1
vote
1answer
40 views

How to solve an Optimization problem with linear as well as Quadratic constraints.

I want to solve the following problem, \begin{equation} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & \mathbf{x^T}\mathbf{Px} \\ & \text{subject to} & & ...
1
vote
1answer
50 views

Using the Gauss-Seidel method, will the matrix A converge

Just came back from my Numerical Analysis midterm, posting up the questions and my solutions for an estimation as to how I did. If you were to perform the Gauss-Seidel method on a matrix $A$, where ...
1
vote
1answer
80 views

Partial QR factorization to solve least squares problem

I'm trying to understand how to solve a least squares problem of the form: $$\begin{bmatrix}A& B \end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = [b]$$ where I only explicitly solve for $y$ and ...
1
vote
1answer
109 views

Minimizing the Determinant

I would like to minimize the determinant of the following matrix, det(A) $A = (VV^T+\lambda I)^{-1}$ and $\lambda$ is set to be very small.
1
vote
1answer
175 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 ...
1
vote
1answer
53 views

Prefactoring to solve many similar linear systems

I am designing an algorithm that needs to solve many (large) linear systems of the form $$\Phi^\top D_i\Phi \vec x_i=\vec r_i,$$ where $\Phi\in\mathbb{R}^{m\times n}$ with $m>n$ is fixed. We will ...
1
vote
1answer
49 views

What is the range of this function

Let $\lambda_{1}(X)$ be the larger eigenvalue of the $2$ eigenvalues of a symmetric matrix X. For fixed real numbers $a,b,c,d$, what is the range of $\lambda_{1}\left(diag\left(a,b\right)-U\cdot ...
1
vote
1answer
357 views

How to find the Householder transformation?

Assume $x=(1,0,4,6,3,4)^T$. Find a Householder transformation and a positive number $\alpha$ such that $Hx=(1,\alpha,4,6,0,0)^T$. I'm sorry that I don't know how to start with this problem. A ...
1
vote
1answer
87 views

Eigenvalues of discretized linear integral operator

Suppose I have the following kernel operator: $Af(x) = \int_{-1}^1 K(x-y)f(y)dy$ which is also positive and compact. Hence, it has a countable set of positive eigenvalues. Suppose those eigenvalues ...
1
vote
1answer
164 views

Limiting Degrees of Freedom in 3D Point Registration

I'm search for some assistance in my application of Arun's algorithm for registration (fitting) of two 3D point sets using the Singular Value Decomposition: ...
1
vote
1answer
59 views

Help regarding a weird Matrix

Hi I have a matrix of the following form arising by discretization of a system of PDEs. I am working to get the invertibility of the Matrix. Can some one help me or at least give me some reference on ...
0
votes
1answer
57 views

Finding the smallest max eigenvalues for related matrices?

While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before. Suppose you have two symmetric $n$ x $n$ matrices in the form ...
0
votes
1answer
44 views

Unique least square solutions

There is a theorem in my book that states: If $A$ is $m\times n$, then the equation $Ax = b$ has a unique least square solution for each $b$ in $\mathbb{R}^m$. But can we find a counter-example to ...
0
votes
1answer
41 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
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
1answer
27 views

Using Givens Rotation on a vector

Say we have a vector v=$[3\ 0\ 4]$. Find a 3x3 orthogonal matrix Q such that only the second component of Qv is nonzero and such that this component is also positive. Is Q unique? I tried ...
0
votes
1answer
47 views

Show that the iteration $x_{n+1} = x_n - 2\frac{f(x_n)}{f'(x_n)}$ converges quadratically to $x_*$ provided $x_0$ is sufficiently close to $x_*$

We have the following conditions for the above slightly-modified Newton's method iteration: $f$ is a real function of one real variable $f''$ is Lipschitz continuous $f(x_*) = f'(x_*) = 0$ I also ...
0
votes
1answer
48 views

Numerical Linear Agebra

how to Prove the backward stability of the inner product ? ...
0
votes
1answer
43 views

Householder Reflection

I am working on algorithms for SVD by first performing Householder transformation. I got my algorithm to work but I'm trying to gain a better intuition of it. My understanding is that the ...
0
votes
1answer
36 views

Is it possible to solve a system of equations comprising FFTs?

Consider the following known matrices, A, B, C and these unknown matrices X,Y, all of which comprise values in the Real domain. Also consider $F(x)$ as the *Fast Fourier Transform function* (the ...
0
votes
1answer
54 views

Inverse Square root of a rectangular matrix

I am trying to compute the inverse square root ($X^{-1/2}$) of a $n \times p$ matrix with $n > p$. I was wondering if we can compute it via SVD just as we do it for square diagonalizable matrices ...
0
votes
1answer
23 views

Residual norm for iterative scheme

Consider a linear system $A\vec{x} = \vec{b}$, where $A \in \mathbb{R}^{m\times{}m}$ is non-singular and positive definite. Given the following iteration scheme $\vec{x}^{(k+1)} = \vec{x}^{(k)} + ...
0
votes
1answer
59 views

Can a 6-arm star be convex

Please help me with the following question. Suppose that the constant level contours of some function $V:\mathbb{R}^{2} \rightarrow \mathbb{R}$ have the shape of a symmetric 6-arm star. Can such a ...
0
votes
1answer
56 views

Fast Gauss-Seidel convergence on low rank matrices

I stumbled upon the following remarkable fact when experimenting with the Gauss-Seidel iterative solver: First I construct a low-rank symmetric positive semi-definite matrix $A = M^TM$ with M a ...
0
votes
1answer
60 views

Completeness of eigenvectors of Hermitian Matrix.

How do you show that eigenvectors of a Hermitian matrix form a complete set of basis?
0
votes
1answer
53 views

Rate of Convergence of Generalized Iterative Method

Consider the generalized iterative method for finding polynomial roots: $z_{k+1}=z_k +d\frac{(1/p)^{(d-1)}(z_k)}{(1/p)^{(d)}(z_k)}$ where d is a positive integer. Note that Newton's Method is a ...
0
votes
1answer
102 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$ ...
0
votes
1answer
15 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
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: ...
0
votes
1answer
135 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
199 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 ...
0
votes
1answer
55 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 ...
0
votes
1answer
85 views

matrix positive semidefinite

If $n \times n $ matrices $A, B$ are positive semi-definite, matrices $P$ and $Q$ are $n\times p$ and $n\times q$ matrices and their column vectors are orthogonal, which is to say $$P^{T}P=I_{p\times ...
0
votes
1answer
43 views

Simple question about equivalence of two forms of PCA as trace maximization over an implicit distribution

This may be a soft question of sorts. One formulation of principal component analysis is trace maximization: $$\arg\max_U \mathbb{E}_x \ [tr(U^Txx^TU)],$$ for $U^TU\le I$ and we assume that there is ...
0
votes
1answer
25 views

Given an M x N matrix, is there a way to produce an orthogonal set of N vectors of length M, where M < N?

Gram-Schmidt orthogonalization would only use the first M vectors to generate a basis of size M x M.
0
votes
1answer
69 views

Matrix existence..

How to prove that for any matrix $A\in \mathbb R^{m\times n}$ ($m\geq n$) such that $rank(A)=r$ there exists a nonsingular matrix $P$ and an orthogonal matrix $U$ such that, \begin{align*} A=U\Gamma ...
0
votes
1answer
108 views

Numerical linear algebra (pseudoinverse of a matrix)

Let $A$ be the matrix: $$\left(\begin{matrix} \alpha I_{n} \\ \beta I_{n} \end{matrix}\right)$$ where $\alpha,\beta\in\Bbb C$ are not both zero. Derive (a) the (reduced) QR factorization of $A$ ...
0
votes
1answer
87 views

Iterative Method for a special kind of Sparse Matrix

I've the following problem.I've a sparse square Matrix $\bf M$. I can write $\bf M$ as: $${\mathbf M} = \begin{bmatrix}\mathbf A_{11} & \dots & \mathbf A_{1n} \\ \vdots & \ddots & ...
-1
votes
1answer
171 views

Positive linear combination of vectors to produce a positive vector

Given a list of vectors, I want a linear combination with positive coefficients that produces a final vector with only positive values (EDIT: this final vector is unknown; any positive vector is ...