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

learn more… | top users | synonyms

0
votes
1answer
31 views

Effects of Scaling on Matrix Norms

I feel as though is a very stupid question, but I'm struggling to muddle through it so here I am. For Gauss-Seidel methods one way to formulate the convergence requirement is that given the system $...
0
votes
1answer
38 views

Solve $a-1.73d=0, b-1.73d=0, c-1.73d=0, a+b+c -1.73d=0$ [closed]

How can we find nontrivial solutions of the homogeneous equation $$a-1.73d=0, b-1.73d=0, c-1.73d=0, a+b+c -1.73d=0$$ I need to find the values of $a,b,c$ and $d$. When I tried with Gauss ...
0
votes
1answer
10 views

Stochastic matrix relating to power method

I dont quite understand this question that I am doing some practice questions for and was wondering if someone could help explain it. The question is a s follows: "Let $P$ be the stochastic matrix ...
1
vote
0answers
23 views

What is the opposite of “sparsity” in a matrix?

If a sparse matrix has only 1% non-zero entries, I find it weird to speak of "1% sparsity". In particular, "increasing sparsity" goes along with a smaller percentage of non-zero entries, so this is ...
1
vote
1answer
24 views

Derivative of Lattice Laplacian

The lattice Laplacian is defined as, $$ \nabla_L^2x_j \equiv \frac{x_{j+1} - 2x_j + x_{j-1}}{a^2} $$ where the lattice spacing, $a$, is a constant. The derivative, with respect to $x_i$, then gives, ...
1
vote
0answers
27 views

Directly solving non-square subproblem of linear system

I have a large sparse linear system $$\begin{pmatrix} A & B\\ C & D \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} f \\ g \end{pmatrix}$$ which ...
0
votes
2answers
57 views

Understanding power method for finding dominant eigenvalues

The power method aims to find the eigenvalue with the largest magnitude. Does magnitude still have the same meaning in this context? If so, can't we tell from the outset which eigenvalue is the ...
1
vote
1answer
36 views

How was this least squares polynomial obtained (solution provided)

Obtain a least squares polynomial of degree 2. $$ \begin{array}{c|lcr} x & \text{0} & \text{0.25} & \text{0.5}& \text{0.75}&\text{1} \\ \hline y & 2.9646 & 3.1826 & 3....
0
votes
0answers
12 views

Why Gauss-Seidel iteration is a projection method

Yousef Saad's iterative method for sparse linear systems says Jacobi, GS, SOR are all projection methods. for example GS is a projection method with $\mathcal K= \mathcal L =\{e_i\}$ (project on $\...
3
votes
4answers
206 views

Solution to this complex number equation

Solve $z^5 +32 =0$ My attempt : $$z^5 = -32$$ Multiply the powers on both sides by $\frac{1}{5}$ we get $$z = 2 * (-1)^\frac{1}{5}$$ Now I'm stuck at this step I don't know how to ...
0
votes
1answer
28 views

Preconditioner operator

hope you can help me. I have learned that a preconditioner is a matrix $P$ such that when it is applied to a system $A \mathbf{x} = \mathbf{b}$, the spectral properties of the matrix $P^{-1} A$ are ...
0
votes
1answer
21 views

Preconditioning : ILU($\emptyset$) factorization and SSOR relation?

Let's suppose we have a matrix A = D - L - U , where D,L,U are diagonal , strictly lower and strictly upper triangular,respectively. Generally the preconditioning matrix, according to SSOR(Symmetric ...
2
votes
2answers
88 views

Cholesky decomposition of a covariance matrix with swapped order of variables

Could you please let me know if there is a quick way to recompute result of a Cholesky decomposition of a covariance matrix, if the order of variables was switched to put a different variable as #1 on ...
1
vote
0answers
31 views

Sensitivity of Eigenvalues with invertibte matrix

Let $A$ a matrix having a set of eigenvectors $\{v_1,\ldots,v_n\}$ linearly independent with $\{\lambda_1,\ldots,\lambda_n\}$ eigenvalues associated. Let $\lambda$ eigenvalue of the perturbed matrix $...
1
vote
1answer
20 views

Matrix similar and unitarily diagonalizable

Let $A,B \in R^{n \ x \ n} $ similar and unitarily diagonalizable. Prove that there $Q$ unitarily such that $Q^{H}AQ=B$
3
votes
0answers
38 views

SVD as a solution to linear least squares

I'm a little confused about the various explanations for using Singular Value Decomposition (SVD) to solve the Linear Least Squares (LLS) problem. I understand that LLS attempts fit $Ax=b$ by ...
1
vote
1answer
43 views

Task with using of A Linear Operator

Population of slithy toves living in severe and adverse conditions, subject to the following rules: a) On average, only half toves survive the first year of life, half of the remaining survives in ...
1
vote
0answers
37 views

Create a matrix of four-dimensional space rotate counterclockwise by the angle π / 3 around the plane

Create a matrix of four-dimensional space rotate counterclockwise by the angle $\frac{π}{3}$ around the plane \begin{cases} x − y + t = 0,\\[2ex] y + z + t = 0 \end{cases} on the basis of unit ...
0
votes
1answer
37 views

Undestanding SVM

I am the moment trying to understand how SVM works.. I understand the concept of finding a seperating hyperplane with the highest margin, but i do not understand how it works in mathmatically. Mor ...
0
votes
0answers
24 views

Complex, symmetric linear equations

What is the fastest numerical method to accurately solve complex, symmetric linear equations? Preferably, with a link to a Fortran code. The dimension is about 100-200 variables. To be more explicit, ...
0
votes
1answer
47 views

SVD and Low-rank approximation

In the proof of Low-rank approximation by Trefethen & Bau, It is written: Theorem 5.8 : A is an $m \times n$ Matrix. For every $v$ with $0 \leqslant v \leqslant r$, define $$ A_{v}=\...
1
vote
1answer
42 views

Data structure for a symmetric $n\times n$ matrix

Suppose you are given a symmetric matrix $A\in\mathbb{R}^{n\times n}$ and consider the computation of the matrix vector product $A u \rightarrow v$ where $u\in\mathbb{R}^n$ is given and $v\in\mathbb{R}...
0
votes
0answers
68 views

What is the fastest known algorithm for finding eigenvalues?

What is the fastest known algorithm for finding eigenvalues? Second and third fast are also of interest if they are simpler, basically anything better than the standard solve characteristic polynomial ...
5
votes
2answers
72 views

Numerical Calculation of Eigenvalues of a large real Symmetric tridiagonal matrix

If I have an $N \times N$ matrix where every entry is zero except for along the super-diagonal and sub-diagonal, where the each entry is the conjugate of the last, like the following $5 \times 5$ ...
0
votes
0answers
26 views

Question on SVD Uniqueness Proof

I have problem understanding the proof of uniqueness for SVD by by Trefethen & Bau. If the lengths of the semi-axes of the hyper-ellipse are distinct, then semi-axes themselves are ...
0
votes
1answer
38 views

Household reflector or transformation

Let $A\in\mathbb{R}^{n\times k}$, $n\geq k$, and $rank(A) = k$. Consider the use of Household reflectors, $H_i$, $1\leq i\leq k$, to transform $A$ to upper trapezoidal form, i.e., $$H_{k}H_{k-1}\ldots ...
2
votes
3answers
69 views

What is the significance of reversing the polarity of the negative eigenvalues of a symmetric matrix?

Consider a full rank $n\times n$ symmetric matrix $A$ (coming from a set of physical measurements). I do an eigendecomposition of this matrix as $$A = E V E^T$$ Most of the eigenvalues are positive, ...
0
votes
0answers
43 views

Linear system equations

I need to get, preferably by a numerical method, a solutions of: $$\left\{\begin{array}{lll} 2\sum_{i=1}^n b_{ik}x_i+x_{n+1}=0&\text{for}& k=1,2\ldots,n\\ \sum_{i=1}^n x_i=0 \end{array}\right.$...
0
votes
1answer
30 views

Vector norm lemma and proof

I have a question from Numerical linear algebra book by Trefethen & Bau : Let $\|\cdot\|$ denote any norm on $C^m$. The corresponding dual norm $\|\cdot\|'$ is defined by the formula $\|x\...
0
votes
1answer
24 views

[Part of a system of linear equations!]: Find $B$ such that $A = B\times C$, but $C\times C'$ is non-invertable

I have the following Equation: $A = B\times C$ $A$ is a $(N\times 1)$ Known Matrix $B$ is a $(N\times M)$ Unknown Matrix, where $N>M$ $C$ is a $(M\times 1)$ Known Matrix $C\times C'$ is a non-...
0
votes
1answer
20 views

Elementary reflector $Q$ is orthogonal iff

Recall that an elementary reflector has the form $Q = I + \alpha xx^T\in\mathbb{R}^{n\times n}$ with $\|x\|_{2}\neq 0$. Show that $Q$ is orthogonal iff $$\alpha = \frac{-2}{x^Tx} \ \ \text{or} \ \ \...
0
votes
0answers
24 views

Query about the Moore Penrose pseudoinverse method

I have recently discovered the Moore-Penrose psuedoinverse method, and I am currently testing the waters with it. I noticed if I have a system, say $$a_1x_1=0$$ $$a_2x_1+a_3x_2=0$$ $$\vdots$$ $$...
1
vote
0answers
45 views

Dual Norm proof

Let $\|.\|$ denote any norm on $C^m$. The corresponding dual norm $\|.\|'$ is defined by the formula $\|x\|' = sup_{\|y\|=1}|y^*x|$. (a)Prove that $\|.\|'$ is a norm? (b) Let $x, y \in C^m $ with ...
1
vote
1answer
56 views

If the determinant of a matrix goes to infinity, does it means it has no inverse?

Context I have a linear time-invariant (single-input, single-output) system in state space representation (https://en.wikipedia.org/wiki/State-space_representation#Linear_systems): $$ \mathbf{x'}(t) ...
0
votes
1answer
18 views

Computing $PAQ = LU$ using Gaussian elimination with complete pivoting

Suppose $PAQ = LU$ is computed via Gaussian elimination with complete pivoting. Show that there is no element in $e_i^{T}U$ i.e., row $i$ of $U$, whose magnitude is larger than $|\mu_{ii}| = |e_i^{T}U ...
0
votes
1answer
21 views

Matlab algorithm for non-orthogonal diagonalization of symmetric matrices

I need to find a basis in which the symmetric bilinear form given by the n x n symmetric matrix which has 2's along the diagonal and 1's everywhere else becomes the identity. That is, if S denotes ...
0
votes
0answers
41 views

Numerical method for solving equation with $u \frac{\mathrm{d}u}{\mathrm{d}x} + u$

I'm looking for a finite difference method to solve $$a(x) u \frac{\mathrm{d}u}{\mathrm{d}x} + u = b(x)$$ where $u(0) = c$. I tried to do a lagging convergence on the $u$ ie $$a(x) u^{(n)} \frac{\...
0
votes
0answers
19 views

Gauss Seidel - Finite Element Method

I am solving an equation using finite element method, and for that I have to use Gauss Seidel to invert a matrix. In Gauss Seidel I am using a "while" which breaks if the absolute error reaches the ...
0
votes
1answer
16 views

Gauss transforms to factor $A = LU$

Consider a symmetric matrix $A$, i.e., $A = A^{T}$. Consider the use of Gauss transforms to factor $A = LU$ where $L$ is unit lower triangular and $U$ is upper triangular. You may assume that the ...
0
votes
2answers
49 views

Condition number for each variable

Condition number of a matrix tells us how viable it is to solve $Ax=b$ $$A= \begin{bmatrix} 1.001&1\\ 1&1 \end{bmatrix} $$ Is a matrix that would be difficult to solve numerically. However ...
1
vote
1answer
33 views

Numerical Range of A and A transpose.

I was playing around with the numerical range [NR] (or field of value) of a matrix $A \in \mathbb{C}^{n\times n}$ lately. And was actually looking for a proof to show: \begin{equation} A=A^H : F(A) = ...
0
votes
1answer
26 views

Write column form elementary matrix in terms of element form elementary matrices

Recall that any unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ can be written in factored form as \begin{equation} L = M_1 M_2\ldots M_{n-1} \end{equation} where $M_i = I + l_i e_i^{T}$ ...
1
vote
1answer
32 views

Numerical solution of heat equation on periodic domain

Consider the steady heat equation $\nabla\cdot(k(x) \nabla u)=f$ in two dimensions on a periodic domain, say $[0,1]\times[0,1]$. My goal is to solve it numerically with standard central 5-points ...
1
vote
1answer
27 views

Gaussin Elimination preserves S.P.D.

Let $A \in \mathbb{R}^{n \times n} $ be symmetric positive definite with positive diagonal entries. I'm trying to show that at each step $m$ of gaussian elimination $$ a^{(m+1)}_{ij} = a^{(m)}_{i,j} ...
0
votes
0answers
16 views

Different ways to leave linearly dependent vectors of a set of vectors

Let a set $S=\left\{ {{\mathbf{v}}_{i}}:i\in \mathbb{Z}_{n}^{+} \right\}$, where $\mathbb{Z}_{n}^{+}=\left\{ 1,2,...,n \right\}$ and ${{\mathbf{v}}_{i}}\in {{\mathbb{R}}^{m}}$ for each $i\in \mathbb{Z}...
0
votes
0answers
24 views

absolute value matrix and derivation of A^1 b

I have a question who could I solve the following sentence? Given is the vector $\vec{b} \in \mathbb{R^n}$ and the function $f : GL(n,\mathbb{R}) \to \mathbb{R}^n$ with $f(A) = A^{-1}b$. Then ...
1
vote
0answers
15 views

why does matrix balancing improve the linear systems condition number of the eigenvector matrix?

Matrix balancing or diagonal scaling, where at each iteration we choose a diagonal matrix so that the row and column norms are approximately equal (Osborne, 1960, Parlett and Reinsch, 1969, many ...
0
votes
1answer
36 views

Matrix-free conjugate gradient

In the conjugate gradient method for solving $Ax = b$, to update the search direction $p$ you would need to evaluate the matrix-vector product $Ap$, i.e. making sure that each search direction are A-...