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

learn more… | top users | synonyms

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. ...
3
votes
1answer
130 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 ...
3
votes
1answer
123 views

How to solve this system of 3 equations with 3 variables?

I stumbled upon this system with constants $a_{i,j}>0$ that I want to solve for $x,y,z \in\mathbb{R}$: \begin{align} a_{2,1}y+a_{3,1}z=& x(y+z) \\ a_{1,2}x+a_{3,2}z=& y(x+z) \\ ...
3
votes
1answer
84 views

Understanding higher order SVD

Can someone explain the singular value decomposition of a tensor (maybe a 3 dimensional matrix) with an example? It is intuitively difficult to the get the meaning from just the formulas. On a ...
3
votes
1answer
117 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
1answer
437 views

Trace Minimization of Covariance Matrix

Given a matrix X whose rows contain observations collected at some locations. Can someone explain how trace minimization of covariance matrix $XX^T$ can lead to orthogonal / mutually independent ...
3
votes
1answer
223 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
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
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$ ...
2
votes
1answer
105 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
194 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 ...
2
votes
1answer
67 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
145 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
59 views

Solve quadric equation system

How to solve this? For given real and symetric matrices $A_1,A_2,A_3,A_4\in\mathbb{R}^{4\times4}$ find $x\in\mathbb{R}^4$ $$x^TA_1x=0$$ $$x^TA_2x=0$$ $$x^TA_3x=0$$ $$x^TA_4x=0$$
1
vote
1answer
41 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
48 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
41 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
65 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
101 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
134 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
144 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 ...
1
vote
1answer
56 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
440 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
106 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
174 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
60 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
35 views

How does the Simplex method of solving LPs use the starting solution?

Say one looks at the LP (in slack form) and sees that assigning $0$s to all the non-basic variables doesn't give a valid solution but some other non-trivial assignment of values to the non-basic ...
0
votes
1answer
67 views

Solve Bratu problem using Python

I am going crazy trying to solve the Bratu problem using Python: $$y''(x)+ e^{y(x)} = 0, \quad \lambda = 1, \quad x \in(0,1),$$ $$y(0) = y(1) = 0$$ I have to solve this using the tridiagonal ...
0
votes
1answer
23 views

What is the computational cost of reduced row echelon and finding the null space?

I'm taking computational linear algebra, and haven't been able to find too much information about the computational cost (in terms of m=rows and n=cols) of these two routines: Reduced Row Echelon ...
0
votes
1answer
51 views

How do I find transformation matrix with respect to given basis in the domain and/or the codomain, given the transformation in the standard basis?

I´m being given a linear transformation, for which I can find the standard basis in the domain and codomain; but then, the book ask to find the associated matrix related to a new basis for the ...
0
votes
1answer
41 views

An algorithm of solving a non-homogeneous linear equation by random matrices

I'm looking for the proof of the following numerical algorithm. Suppose I want to solve a non-homogeneous linear equation \begin{equation} A x = b \end{equation} The matrix $A$ is non-invertible and ...
0
votes
1answer
24 views

Function from one Null space to Another

Suppose a single vector space over $R$ of degree $n$, and two matrices $A, B$ of arbitrary row size, but col size $n$, s.t. their individual null spaces are linear subspaces of this vector space. Is ...
0
votes
1answer
69 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
0answers
48 views

Is there any risk to transform to $(B^{T} \otimes A)\operatorname{vec}(X)=\operatorname{vec}(C) $ for solving $AXB=C$ for X

To solve the equation $AXB=C$ for X, we can use the property of vec operator and kronecker product to transform to $(B^{T}\otimes A)\operatorname{vec}(X)=\operatorname{vec}(C)$, where ...
0
votes
0answers
78 views

Shear decomposition

Is there an algorithm for decomposing a square matrix (or a similar matrix to it) in to shear and diagonal matrices? All the usual decompositions (Schur, SVD, QR, LU, etc.) don't seem to help. ...
0
votes
0answers
92 views

Can antiunitary symmetry be used to calculate determinant of a matrix

Suppose I have some $N \times N$ complex matrix $A$, that commutes with some antiunitary operator $U$ that satisfies $U^2 =-1$. It can be shown that $\det(A)\ge 0$ , because for every eigenvector ...
0
votes
0answers
44 views

Derivative of $H$ with respect to $W$

I am trying to solve a generalized linear squares model with the following form: $\hat{Y}= X(X'\Omega^{-1}WX)^{-1}X'\Omega^{-1}WY $ $ H= X(X'\Omega^{-1}WX)^{-1}X'\Omega^{-1}W $ $ \Omega$ is the ...
0
votes
0answers
136 views

Divide and conquer possible on linear equation systems?

Suppose a 4-connected regular grid $$\mathcal{G}=(\mathcal{E},\mathcal{V}),$$ where $\mathcal{E}$ and $\mathcal{V}$ denote the set of edges and vertices of that grid, respectively. Given this ...
0
votes
0answers
74 views

relative error relation

Let $x$ be a non-null quantity. Let $\hat{x}$ be its approximation. I am trying to find the relation between: $\frac{\left | x-\hat{x} \right |}{\left | x \right |}$ and $ \frac{\left | x-\hat{x} ...
0
votes
0answers
41 views

Issues with the value of the last element in Cholesky decomposition

I am trying to calculate the Cholesky decomposition of a precision matrix. I was expecting a Lower triangular matrix $L$ where $L_{ii}>0$ for all $i$. However, the last element in the diagonal is ...
0
votes
0answers
309 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $F(x)$ $F(x) = \sum_{i=1}^{M}||x_{i+1} - x_i - K(\frac{x_{i+1} + x_i}{2})||^2 + ||x_1-c_1||^2 + ||x_N-c_2||^2$ , where $x$ is a vector of $N$ scalars, $c$ are ...
0
votes
0answers
246 views

Householder Transformation

Let $\mathbf{a}\in\mathbb{R}^{n}$ be a non-zero vector. Develop a numerically stable procedure to compute a Householder transformation P such that $$P\mathbf{a}=\left(\begin{array}{c} ...
0
votes
0answers
64 views

Can this be expressed as an LLSQ problem? $||Ax - b|| = c$

I'm trying to minimize the following: $||Ax - b|| - c$ where: $A$ : $K \times M$ matrix $x$ : $M \times N$ unknowns ($M$ $N$-dimensional vectors) $b$ : $K$ $N$-dimensional vectors $c$ : $K$ ...
0
votes
0answers
113 views

Efficient principal pivots

Background I'm working on a numerical linear algebra package in C#. I'm trying to implement a variety of "principal pivoting" methods to solve optimization problems (specifically linear ...
0
votes
0answers
57 views

Diagonalising a huge matrix of symbolic objects

I have to diagonalise this HUGE $9\times 9$ matrix with symbolic entries which are made up of three independent variables. Can you please give me a reference as to how to do such a thing ...
0
votes
0answers
94 views

Does a single Gauss-Seidel iteration lead to unique coordinates?

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$, and $x,y\in\mathbb{R}^{n\times 2}$ are ...
0
votes
0answers
45 views

Lower Rank Matrix

Given I have a matrix A of rank 3. I want to create a matrix of Rank 2 which is closest to A in the $ {l}_{2} $ / Frobenius norm. Let's call this matrix F. Is easy to achieve by the SVD, namely, if $ ...
0
votes
0answers
143 views

Singular value decomposition, possible property

Suppose a singular value decomposition on matrix $P\in\mathbb{R}^{n\times m}$ is given, $P=U\Sigma V^T$ with $U=[u_1,\dots, u_n]\in\mathbb{R}^{n\times n}$, $u\in\mathbb{R}^{n}$, containing the ...
0
votes
0answers
174 views

Estimating a solution with the Jacobi Method for solving Ax = b

I'm trying to understand how the Jacobi method works and would appreciate a walk-through of the method with a very very simple example. In particular, I don't fully understand how one goes from the ...