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

learn more… | top users | synonyms

0
votes
0answers
22 views

Linear algebra <perhaps an application of Gordan' Theorem>

Question. Let $a_1,...a_n\in\{0,1,-1\}^m$ and $\sum a_i=(1,...,1)$. Is there a permutation $\tau$ of $\{1,...,n\}$ Such that for each $k\in \{1,...,n\}$ the vector $\sum_{i=1}^k a_{\tau (i)}$ has ...
1
vote
0answers
42 views

Numerically stable SVD

In this question regarding SVD, it is explained why eigen decomposition of $ A^tA $ is not numerically stable compared to "direct SVD algorithms". Since the former is the algorithm I'm most familiar ...
2
votes
0answers
17 views

Reference request for finite difference method

I am trying to use finite difference method to solve the minimizing problem $$ J[u]=\min_{u\in BV(Q)}\{\|u-f\|_{L^1(Q)}+|u|_{BV(Q)}\} $$ where $Q=(0,1)\times (0,1)$ is a uint square and ...
1
vote
1answer
32 views

What happens if the power method is applied with a starting vector $q=c_2 v_2+…+c_n v_n$ in the presence of roundoff errors?

Supose $\{v_1,...,v_n\}$ is an eigenvector basis and $|\lambda_1|>|\lambda_2|>\ldots >|\lambda_n|>0$, so, my question is, if our starting vector $q \in span\{v_2,\ldots,v_n\}$ and in the ...
1
vote
1answer
39 views

What are some Applications of Hermitian Positive Definite matrices?

I am learning about Hermitian positive definite matrices and the way that they can be decomposed with Cholesky decomposition. I have learned that these matrices deserve special attention for how often ...
0
votes
1answer
42 views

Iterative method to compute only the positive eigenvalue's and corresponding eignevectors of a very large matrix?

I have a very large dense matrix (~10000 X ~10000) which is not full rank . I want to compute only the positive eigenvalues and corresponding eigenvectors instead of computing all of them. I have ...
0
votes
1answer
31 views

How to link the eigenvalues to the components from PCA

I have a difference matrix from daily changes which I use to construct a covariance matrix. On this covariance matrix I use the power method to get the eigenvalues. The power method yields exactly the ...
0
votes
0answers
18 views

Is my QZ-Step as postulated in the paper?

I am working with the paper An algorithm for generalized matrix eigenvalue problems from C.B. Moler and G. W. Stewart (paper available here: ...
1
vote
0answers
28 views

Numerically finding eigenvalues of a Volterra operator of first kind

I'm looking for a solution to the following problem - $\int_{-\infty}^{\infty} K(x-y) f(y) = \lambda f(x)$ Consider $K(x-y) = \left\{ \begin{array}{lr} e^{-(x-y)} & : x > y \\ 0 & : x ...
1
vote
0answers
26 views

Ideas for expressing the inverse of matrix quadratic form $CAC^T$

I want to find an expression for the inverse of the matrix system $Z=CAC^T$, where $A \in \mathbb{C}^{n \times n}$ is block diagonal with dense blocks, and $C \in \{-1,0,1\}$ with dimension $m \times ...
2
votes
1answer
37 views

Solving a system of polynomials in $N$ variables

Suppose I am given some non-negative constants $(C_p)_{p=1, ..., l}$ and I would like to find an integer $N$ and vector $v \in R^N$ such that $$ \sum_{i=1}^N (v_i)^p = C_p $$ for $p=1, ..., l$. Can ...
1
vote
0answers
39 views

Eigenvalues after Givens-Rotation

Im just validating my own Code of a Givens-Rotation in Matlab. Therefore i let matlab compute the Eigenvalues after each Givens-Rotation. I am wondering why the Eigenvalues computed by matlab are ...
1
vote
2answers
108 views

Solving a matrix equation using numerical optimization

To my knowledge, if $A \in \mathbf{S}^n_{++}$, then given any $b \in \mathbb{R}^n$, the system of linear equations $Ax = b$ has a unique solution $x^* \in \mathbb{R}^n$. Moreover, the solution $x^* ...
1
vote
0answers
42 views

Simplifying the Generalized Eigenvalue Problem

Let $\Sigma_1$, $\Sigma_2$ be symmetric positive-definite real $n\times n$ matrices. We want to solve the generalized eigenvalue problem $$ \Sigma_1V=\Lambda\Sigma_2V, $$ where $\Lambda$ is the ...
0
votes
1answer
34 views

Use the Forward Difference method to approximate the solution to the following PDE?

Use the Forward Difference method to approximate the solution to the following PDE: $$ u^3\frac{\partial u}{\partial t}-x^2u\frac{\partial^2u}{\partial x^2}=2x^8t^7+6x^6t^5+4x^4t^3 $$ for $0\le ...
0
votes
0answers
15 views

QZ-Algorithm: how to simultaneously generate the upper triangular form

I need to calculate the Eigenvalues of a generalized Eigenvalue Problem. To achieve this, i wanted to use the QZ-Algorithm, which avoids calculating the inverse of a Matrix. This quite useful, because ...
2
votes
4answers
67 views

Inverse Chebyshev Recurrence

The Chebyshev polynomials (of the first kind) are a sequence of polynomials defined recursively by $$ \begin{cases} T_{0}(x) = 1 \\ T_{1}(x) = x \\ T_{n}(x) = 2xT_{n-1}(x) - T_{n-2}(x) \end{cases} $$ ...
1
vote
0answers
54 views

complex rank-one update

I'm trying to find the eigendecomposition of a rank-one update to a complex matrix $D + uv^T$. The matrix $D$ is diagonal, but not the identity. It has unique imaginary entries along the diagonal. ...
1
vote
0answers
39 views

Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, ...
0
votes
0answers
37 views

Givens-Rotation from the right

i need to get a Givens-Rotation, which zeros a matrix entry when multiplied from the right side. I did already look at this topic givens rotation from right side but i could not really understand the ...
5
votes
1answer
18 views

Proving a property about Gauss-Seidel

This is a homework problem, so please give hints or tips instead of full answers. The problem is as follows: Let $G$ be the iteration matrix of the Gauss-Seidel method; i.e. $$G=I-(D-L)^{-1} ...
0
votes
0answers
8 views

Conversion of cylindrical harmonic field into space-harmonic field for plane waves

It is well known that a plane wave can be represented by an infinite sum of cylindrical wave function of the form $\varphi^i(\rho,\phi)=e^{\left(-j\beta \rho ...
0
votes
0answers
18 views

PCA when SVD is a skinny SVD

A = m * n matrix. When $m \ge n$, it is easy to see that the V matrix in the full SVD ($A = U*S*V^T$, where U and V are both orthonormal square matrix) and V in a skinny SVD are the same. When $m \lt ...
1
vote
0answers
22 views

Overdetermined system with discrete data.

The setup I have a set of experimental data (subscript 1) which calculates two variables $u_1(x,y,z)$ $v_1(x,y,z)$ I can calculate the three spatial gradients for my two variables ($u_1$ and ...
1
vote
0answers
26 views

QR Algorithm fails under certain conditions

First of all, i have to admit that i am really knew to this numeric stuff. I have to detect two complex Eigenvalues of a Matrix and therefor i implemented some easy QR-Algorithm with MatLab. I am ...
0
votes
2answers
21 views

Special properties in the direct solving of sparse symmetric linear systems

In the area of computational solving of large sparse linear systems, some solvers specialize only on symmetric sparse matrices, be it positive definite or indefinite as compared to general ...
0
votes
0answers
90 views

Linear Algebra Book like Calculus Made Easy

Now, I know that there are a tons of reference requests for Linear Algebra books but mine is very specific: what is a nice, short, concise, simple, to the point book that gets at the heart of Linear ...
1
vote
0answers
31 views

$Az + B\overline{z}$ as a linear operator

Given two matrices $A,B \in \mathbb{C}^{n\times n}$ with fixed $n\in\mathbb{N}^+$, let us consider the operator $$ L:\mathbb{C}^n \to \mathbb{C}^n,\\ L(z) = Az + B\overline{z}. $$ This operator is not ...
1
vote
0answers
22 views

Row degeneracy in systems of linear equations

I am trying to understand the concept of row degeneracy in a system of linear equations, but having trouble understanding this problem. \begin{align} x+2y+z &= 2 \tag{1} \\ 2x+y+3z &=5 ...
0
votes
0answers
43 views

Solving the linear system $XL + L^TX = M$ efficiently

I'm wondering of an efficient way to solve the following system for the symmetric matrix $X$, given a positive semi-definite matrix $S$ and any matrix $M$: $$ LL^T = S $$ $$ XL + L^TX = M $$ $$ (XL) + ...
1
vote
1answer
76 views

Using linear algebra (e.g. matrix) methods to solve a system of linear inequalities

Say we have the equation $Ax>b$, where $A$ is an M-by-N matrix, $b$ is a known vector of length N, x is an unknown vector of length N, and the inequality sign means that each element of $Ax$ is ...
1
vote
2answers
61 views

Positive linear combinations of intervals

Given two intervals at $i\in\{0,1\}$ $I_i=[-a_i,a_i]$ where $0<a_0<a_1=1-a_0<1$ and a third interval $I=[-a,a]$ where $0<a<\frac{1}2$, when is there an $\alpha,\beta\in\Bbb R$ such that ...
1
vote
0answers
13 views

Enforcing additional constraints in linear equation

In a finite element context, I come up with a sparse "stiffness matrix" $A$ and a corresponding RHS $b$. The goal is now to solve $$Au = b$$ Where $u$ is a coefficient vector of the solution. Now I ...
1
vote
0answers
35 views

Solving System of Linear Equations

These are the two known equations: $$\frac{(I_2+I_3)-(I_1+I_4)}{I_1+I_2+I_3+I_4} = \frac{2x}{L}$$ $$\frac{(I_2+I_4)-(I_1+I_3)}{I_1+I_2+I_3+I_4} = \frac{2y}{L}$$ where I know the values of $(x,y,L)$. ...
0
votes
1answer
26 views

Let $f:[-1,1]\to \mathbb{R}$ by $f(x)=x^4$. Determine the polynomial $p_2$ of degree less than or equal to 2 such that $||f-p_2||_2$ is minimal

also compute $||f-p_2||_2$. Write $p_2$ with respect to $\{P_0,P_1,P_2\}$ and $\{1,x,x^2\}$ I know its helpful to show what I have so far but I really don't know where to start. I'm looking at ...
3
votes
1answer
117 views

An Extension to the Generalized Eigenvalue Problem

Given two square matrices $A,B \in \mathbb{R}^{n\times n}$, the generalized eigenvalue problem is finding the scalar $\lambda \in \mathbb{C}$ and vector $x \in \mathbb{C}^{n}$ such that $$ A ...
0
votes
1answer
62 views

Complexity of Newton iteration problem for a d-dimensional problem

If we assume that we have $f:\mathbb{R}^{d} \rightarrow \mathbb{R}^{d}$ and we want to use the Newton iteration method to solve $f(x)=0_{\mathbb{R}^{d} }$. Is there any theorem regarding the ...
1
vote
1answer
24 views

Polar decomposition varient

I have a factorisation to do, and I think that a varient of Polar decomposition will give me what I need, although I'm not sure of the exact form. I have \begin{equation*} \mathbf{y} = ...
0
votes
0answers
52 views

When to use iterative methods for solving systems of linear equation

Iterative methods such as Jacobi, Gauss-Seidel method and successive over relaxation have a very limited field of use - for diagonally dominant matrices. So how they could be used on practice? What is ...
0
votes
0answers
39 views

Implicit Solution of Linear Algebraic Equations with Discontinuities

I am trying to get a reliable algorithm for solving a set of linear algebraic equations involving implicit singularities/discontinuous function. The model equation is: $$ {\bf s}_{n+1} = {\bf s}_n ...
1
vote
1answer
36 views

Generate a random neutrally stable matrix

I need to generate random real matrices such that all eigenvalues have real part equal to 0 -- i.e. random neutrally stable matrices. What's the simplest way to do this? Note that I don't care about ...
0
votes
1answer
22 views

Linear functional and Hessian

Consider the vector space $\mathbb{R}^n$ provided with the usual inner product $<.,.>$. Let $A\in \mathbb{M}_n(\mathbb{R})$ a invertible matrix, $b\in\mathbb{R}^n$ and $J:\mathbb{R}^n\rightarrow ...
0
votes
1answer
25 views

Relationship between centralization and floating-point arithmetic

Suppose I have a problem of least squares where I have $n$ independents regressor variables $x_i$, and suppose I applied the process of centralization and scaling to this variable through ...
2
votes
0answers
42 views

Invertibility of infinite order matrix

how the matrix $[e^{-(x_j-x_k)^2}]$ is invertible where $\{x_j\}$ be any real sequence such that $(x_{j+1}-x_j) >0$ for all $j \in Z$ where $Z$ denotes the set of integers.
0
votes
1answer
18 views

Show if it is lipschitz continuous?

I can't use the mean value theorem to prove this. The problem that I am given is $$ f(x) = (\sqrt{17\pi} )x^2 $$ on the interval $=-10 \le x \le 4$ I know that I have to show that $\lvert ...
0
votes
1answer
36 views

System of linear equations: and a small perturbation

If $Ax=b$ and $Ax'=b'$ where $x'$ and $b'$ are $x$ and $b$ with a small perturbation, the following inequality will always hold: $ (\left\lVert x-x' \right\rVert/\left / \lVert x \right\rVert) \le ...
0
votes
1answer
19 views

Find a diagonal matrix D such that the gershgorin disks of the matrix $B=D^{-1}AD$ do not include the origin

I am given that $$ A= \begin{bmatrix} 3 & 4 \\ -5 & 9 \end{bmatrix} $$ Find a diagonal matrix D such that the gerschgorin disks of the matrix $B=D^{-1}AD$ ...
1
vote
1answer
46 views

Factorization algorithm to solve this system?

What is the best factorization algorithm to solve this system? (Best is intended as more stable) $$ AA^Tx = b $$ x, b vectors
0
votes
3answers
29 views

Show that UV is a unitary matrix?

Suppose $U$ and $V$ are unitary matrices of the same size. Show that $UV$ is a unitary matrix. I looked up the definition for unitary matrices in my notes. It says that A matrix is unitary if $UU^*= ...
0
votes
0answers
27 views

Smallest square problem, $A^*A$ singular?

In our numerics class, we have to solve the smallest square problem $Ax = b$ with $$A = \left( \begin{matrix} 1 & 3 &-4\\ 3 & 9 & -2\\ 4 & 12 & -6\\ 2 & 6 & 2 ...