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

learn more… | top users | synonyms

0
votes
1answer
30 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 $...
2
votes
2answers
525 views

Space spanned by matrices

I have a set of $5$ by $5 $matrices, $M_1,M_2,...,M_{19} ,M_{20}$. I want to try to find a basis from this set and also to find relationships between these matrices. This is how I think I should ...
2
votes
2answers
178 views

compute the bisecting normal hyperplane between two $n$-dimensional points.

I have two points $\mathbf{x_1}$ and $\mathbf{x_2}$, where $\mathbf{x_i}=\{x^i_1, x^i_2, \ldots, x^i_n\}$. I need to find a normal hyperplane $P$ that goes through the midpoint of $\mathbf{x_1}$ and $\...
0
votes
1answer
38 views

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

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
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
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
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
56 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 ...
6
votes
4answers
976 views

Finding nonnegative solutions to an underdetermined linear system

Here's the environment of my problem: I have a linear system of 4 equations in 8 unknowns (i.e. $Ax = b$, where $A$ is $4 \times 8$, $x$ is $8 \times 1$, and $b$ is $4 \times 1$, with $A$ given and $b$...
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 ...
4
votes
0answers
349 views

Optimized way to compute L1 distance matrix

I'm computing distances between two groups of multi-dimensional points giving a matrix of distances pairwise between points. For the L2 (euclidean) distance I can use optimized matrix multiplication ...
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
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 ...
0
votes
0answers
11 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 $\...
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 ...
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 ...
2
votes
1answer
1k 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
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$
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 $...
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
434 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 domain.....
0
votes
1answer
46 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}=\...
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, ...
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$ ...
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, ...
2
votes
1answer
873 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 ...
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 ...
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
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
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
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
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
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$$ $$...
2
votes
4answers
833 views

Non-monotonic decrease of residuals in Conjugate Gradients:

In some of my numerical programming using conjugate gradient solvers, I noticed an alarming problem: The residuals were not monotonically decreasing to zero, but were sometimes increasing. In this ...
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
46 views

$\kappa(B^{-1}A)=\kappa (AB^{-1}) = \frac{\lambda_{\max}(B^{-1}A)}{\lambda_{\min}(B^{-1}A)}$

Prove or disprove: if $A,B$ are symmetric positive definite (s.p.d.) matrices then operator 2-norm condition number $\kappa(B^{-1}A)=\kappa (AB^{-1}) = \frac{\lambda_{\max}(B^{-1}A)}{\lambda_{\min}(B^{...
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
17 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 ...