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

learn more… | top users | synonyms

2
votes
1answer
65 views

show that $\lambda_{max}(B^{-1}A) \leq 1$ (eigenvalues, matrices, preconditioning)

I'm trying to get more familiar with eigenvalues and matrices but struggle to see the following: $\lambda_{max}(B^{-1}A) \leq 1$ $A \in \mathbb{R}^{n \times n}$ is symmetric, positive definite ...
0
votes
1answer
36 views

Backward Euler method and the trapezoidal method are zero-stable [on hold]

Show that backward Euler method and the trapezoidal method are zero- stable. I have no clue to prove the claim. Can anyone give me some hints? Thank you in advance. For someone who don't know ...
9
votes
3answers
1k views

I get a wrong determinant - why?

I'm trying to calculate the following determinant: $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ a_0 & x & a_2 & \dots & a_n \\ a_0 & a_1 & x & \dots ...
1
vote
1answer
32 views

Calculating the determinant by upper triangular reduction - can you check if it's correct?

Exercise: Calculate $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_n \\ -x & x & 0 & \dots & 0 \\ 0 & -x & x & \dots & 0 \\ \dots & \dots & ...
0
votes
0answers
16 views

Minimising two interdependent equations with least squares regression.

Originally, I had a set of points in three dimensional space that I was fitting using linear regression. So my model is $$Y = \alpha A+ \beta B$$ where $Y = \{y_i\}$ is the dependent variable, and ...
2
votes
1answer
48 views

Doubts on inverse power method

I found written that if matrix A is real and you use the Power method to find eigenvalues then "If the matrix and starting vector are real then the power method can never give a result with an ...
0
votes
0answers
17 views

condition number of a matrix with diagonal ones and constant else. [duplicate]

Consider the matrix $$A=\left(\begin{array}{ccccc} 1 & c & \cdots & c\\ c & 1 & \ddots & \vdots \\ \vdots & \ddots & \ddots & c\\ c & \cdots & c & 1\\ ...
1
vote
1answer
71 views

Fastest way to solve linear system with block symmetric banded/Toeplitz matrix

I have a matrix of the following form: The size of the matrix may grow to be large, but the general pattern of being blockwise symmetric and banded (with 5 bands) will always hold. What is the ...
1
vote
1answer
46 views

Finding the Coefficient Matrix of a Spring-Mass System

So as part of a class in numerical linear algebra, we're exploring the topic of banded matrix system. I've come across a problem that involves Hooke's Law, but I'm having a little difficulty ...
0
votes
1answer
28 views

SVD for Seam Carving

Could SVD be used for Seam Carving ? I am making a small program for a uni course and I'm looking for different ways to calculate pixel energy; which made me come across SVD. Among others, I have ...
1
vote
0answers
14 views

How to determine if an algorithm converges for solving Ax = b in practice?

Suppose I am using iterative refinement. I am updating the solution $$x^{(k+1)} = x^{(k)} +p$$ where $Ap = b - Ax^{(k)}$. If $A$ is ill-conditioned, then we can not simply use residual norm or the ...
0
votes
1answer
31 views

How to find a number greater than the largest (smaller than the smallest) eigen value of a matrix efficiently?

I have a symmetric matrix $A$, I want to find a number say $\lambda_1$ which is greater than $\lambda$,i.e. the largest eigen value of the matrix $A$. It doesn't need to be equal to $\lambda$. But ...
0
votes
2answers
30 views

$LU$ Factorization, improving upon stability

I was wondering when we add partial pivoting to an $LU$ factorization to a matrix $A$ it supposedly changes the data structure but improves the overall algorithm since we get better numerical ...
2
votes
0answers
28 views

Iterative methods: What happens when the spectral radius of a matrix is exactly 1?

I know that an iterative method (I'm using Jacobi and Gauss-Seidel in this case) will converge iff the spectral radius (max absolute value of eigenvalues) of its iterative matrix is strictly less than ...
1
vote
0answers
31 views

What is the function of the pivot index vector in Gauss Jordan Elimination with full pivoting?

In numerical recipes, on page 39 (page 4 of the pdf) the following algorithm has been suggested for finding a pivot: ...
2
votes
1answer
41 views

Determining symmetricity of a matrix by multiplying with random vectors?

Stemming from an approach in a hint/answer to this question here. The idea is presented to determining wether a matrix is symmetric or not by measuring the following: $$e = \|({\bf Av})^T - ({\bf ...
1
vote
2answers
81 views

Is there an iterative way to evaluate least squares estimation?

Suppose to have a set of data $\{y_i, u_i\}_{i=1}^m$, where $y_i \in \mathbb{R}$ and $u_i \in \mathbb{R}^n$. The claim is that $$y_i = u_i^\top \theta + \varepsilon$$ where $\theta \in ...
0
votes
1answer
39 views

Prove there exist such that $A = [T]_\beta$ and $B = [T]_\gamma$ [closed]

Let $A$ and $B$ be similar $n \times n$ matrices. Prove that there exists an $n$-dimensional vector space $V$, a linear operator $T$ on $V$, and ordered bases $\beta$ and $\gamma$ for $V$ such that $A ...
1
vote
3answers
42 views

upper bound of a function $n^{1/\log(n)}$

I have the following expression $n^{1/\log(n)}, \quad where \quad n \in [1, 10,000]$. When I solve this numericall, I get the resultant value 2.718282 for all $n \in [2, 10,000]$. On this basis, I can ...
3
votes
1answer
45 views

An exercise with linear maps

I'm solving the following exercise: $\newcommand{\RR}{\mathbb{R}}$ Let $f: \RR^3 \rightarrow \RR^4: (a,b,c) \mapsto (a+2b+c, b+c, a + 2b + 3c, a + b + 2c)$ Find the basis of $f^{-1}(E)$ ...
1
vote
1answer
36 views

Choosing value of ω for SOR

I am learning about successive overrelaxation, and I'm wondering if there is an intuitive reason as to why ω must be between 0 and 2. I know that the method will not converge is ω is not on this ...
1
vote
0answers
50 views

Dynamically equivalent of numerical solution of $y' = f(y)$.

Consider an autonomous system $y' = f(y)$ and a fixed step size $h$. a) Show that the trapezoidal method applied $N$ times is equivalent to applying first half a step of forward Euler, (i.e ...
0
votes
0answers
12 views

matrix optimization problem techniques

I'm looking for some resources on learning techniques commonly used in matrix optimization. For example, minimization of the Frobenius/nuclear/weighted norm of a function of a matrix subject to ...
1
vote
1answer
35 views

Unitary diagonalization of matrices

Can someone tell me whether every square matrix $A\in \mathbb{R}$ unitarily diagonizable? If yes what is a necessary and sufficient condition for a square matrix $A\in \mathbb{R}^{n\times n}$ to be ...
0
votes
0answers
46 views

Beginner Linear Algebra 1 equation with 3 variables

I do not understand what to put into the remaining values. I tried to solve for the y and z like I did for the x, but the system is telling me that is incorrect. Some help would be appreciated
0
votes
1answer
31 views

Is there any Eigen value decomposition, which can be warm-started?

I have a Matrix, $A$ which is positive semidefinite. No consider, $B=A+\Delta$. I have Eigen decomposition of $A$ and $\Delta_{ij}<= \epsilon_1$, $\Vert \Delta \Vert_F <= \epsilon_2$. Is there ...
3
votes
1answer
56 views

$LU$ Factorization

Suppose the $A\in\mathbb{R}^{n\times n}$ is nonsingular and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^TA^{-1}e_j$,i.e., the $(i,j)$ element of $A^{-1}$ in ...
0
votes
1answer
28 views

Is it true that solving a triangular system using forward or backward substitution numerically stable?

The system is $TX = B$, where $T$ is a triangular matrix, $X$ is a unknown matrix, and $B$ is the RHS matrix. I know the system $Tx = b$ is backward stable where $b$ is a RHS vector. Detail check ...
1
vote
1answer
90 views

Best algorithm to compute the first eigenvector of symmetric matrix

Assume that we have a real symmetric matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$ obtained as following : $$\mathbf{A}=\mathbf{N}-\mathbf{P},$$ with $\mathbf{N}\in\mathbb{R}^{n\times n}$ and ...
1
vote
0answers
33 views

Galerkin formulation of 1D linear Schrodinger equation

I am interested in the weak (Galerkin) formulation of the 1D Schrodinger equation: $i u_t−\beta u_{xx}=0$ and $u(x,0)=u_0(x)$. As usual, we do integration by parts which yields: $i (u_t,v)+\beta ...
0
votes
0answers
25 views

Computing a new inverse given information from an earlier inverse:

Suppose I have linearly independent set of vectors $v_1 ... v_k \in \mathbb{R}^{k}$. I can let $B = [v_1 ... v_k]$ and by applying Gaussian elimination on the matrix $$ [ B \ I_k] $$ I end up ...
1
vote
1answer
48 views

Comparing matrix norm with the norm of the inverse matrix

I need help understanding and solving this problem. Prove or give a counterexample: If $A$ is a nonsingular matrix, then $\|A^{-1}\| = \|A\|^{-1}$ Is this just asking me to get the magnitude of ...
1
vote
1answer
18 views

Conditioning in regards to matrix vector product

This program involves the matrix-vector computational primitive $y \leftarrow Ax$ where $x,y\in\mathbb{R}^n$ and $A\in \mathbb{R}^{n\times n}$. A is taken to be dense and banded in the two parts of ...
1
vote
1answer
40 views

Sparse Matrix or Dense Matrix

My task is to implement the inner product and vector triad forms for a dense $A$ in single and double precision. I have successfully implemented the inner product and vector triad form although, I am ...
2
votes
1answer
37 views

Eigenvalue perturbation theory for $(A^TA)(B^TB)^{-1} + (B^TB)(A^TA)^{-1}$

Let $A, B$ be $n \times n$ matrices with full rank. I'm interested in getting a bound on how the smallest eigenvalue of $S = (A^TA)(B^TB)^{-1} + (B^TB)(A^TA)^{-1}$ changes when I perturb $A$ and $B$. ...
1
vote
1answer
34 views

Order of $LU$ factorisation

Can someone tell me how to calculate the order of a) $LU$ decomposition as well as b)the gaussian elimination of a square matrix $A$? I am at a loss ... Given:: $A$ is a $n\times n$ matrix and ...
2
votes
1answer
19 views

Finding linearly independent columns of a matrix when $m < n$

I need to a maximal set of linearly independent columns of a matrix $A$. I've googled a lot and seen various solutions, but none of them seem to work for me. What I've seen so far is 1.- Using ...
0
votes
1answer
18 views

Efficient Row Sum of Factorized Matrix

I am currently computing the row sums of a reduced rank factored matrix by reconstructing a row subset of the original (approximated) matrix. The matrix was factored using SVD: A -> U, S, V -> U, SxV ...
1
vote
1answer
57 views

Matrix-vector product of a banded matrix

Suppose $A\in\mathbb{R}^{n\times n}$ is a banded matrix, i.e., a matrix with all of its nonzero elements on the main diagonal, i.e., $\alpha_{i,i}\neq 0$, the first superdiagonal, i.e., ...
0
votes
1answer
61 views

A generalized eigenvalue problem

The generalized eigenvalue problem likes this: $\begin{pmatrix} 0 & C_{12}\\ C_{21} & 0 \end{pmatrix} \begin{pmatrix} \xi_1\\ \xi_2 \end{pmatrix}=\rho\begin{pmatrix} C_{11} & 0\\ 0 ...
0
votes
1answer
32 views

Backward Stability Lemma

Lemma-Let $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^n$ with components, $\xi_i$ and $\eta_i$, $1\leq i\leq n$, respectively, that are floating point numbers. Computing the inner product $x^Ty$ on a ...
2
votes
1answer
65 views

In common tongue, what is the differences between sparse and dense matrices?

What are the differences with sparse and dense matrices in practice, so as to offer some insight to new learners on a more intuitive level. Obviously everyone knows about the dictionary definition of ...
0
votes
2answers
35 views

Find a spd matrix $C \in \mathbb{R}^{n\times n}$ such that $\langle Cv_i,v_j\rangle = \delta_{ij}$

Let $v_1,\ldots,v_n$ be set of eigenvectors of matrix $A \in \mathbb{R}^{n\times n}$. Find a symmetric positive definte matrix $C \in \mathbb{R}^{n\times n}$ such that $\langle Cv_i,v_j\rangle = ...
0
votes
1answer
45 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}) = ...
0
votes
2answers
45 views

2-norm of the orthogonal projection

So far, I've deduced that if the rank of A is n, then all the columns of A are linearly independent since A has n columns. As a result, m must be greater than or equal to n. In the case that m = n, ...
0
votes
1answer
39 views

Prove or disprove if $µ_0(Bx, x) ≤ (Ax, x) ≤ µ_1(Bx, x), ∀x ∈ R^n$, then $κ(B^{−1}A) ≤ \frac{µ_1}{µ_0}$

Let $A, B ∈ \mathbb{R}^{n×n}$ symmetric. Show that conditional number $$κ(B^{−1}A) ≤ \frac{µ_1}{µ_0}$$ holds, if $B ∈ \mathbb{R}^{n×n}$ is a symmetric positive definite matrix satisfying $$µ_0(Bx, x) ...
0
votes
0answers
33 views

Hilbert Matrix, Gaussian Elimination with varying pivot strategies, and computation error.

I'm doing a project for my Numerical Analysis class about computational error related to Gaussian elimination, gaussian elimination with partial pivoting, and gaussian elimination with scaled partial ...
2
votes
2answers
63 views

From $Ax=\lambda x$, we have $Ax i = \lambda x i$ , where $i^2=-1$??

Actually I found this problem when I met a question, asking me to prove the eigenvector and eigenvalue of real symmetric matrices are all real. I have already proved the eigenvalue part already, but ...
0
votes
0answers
23 views

Matrix approximation

How to solve numerically for non-negative full-rank matrices $P$ and $E$ with the following constraints? $Y$ is a known non-negative matrix with $G$ rows and $N$ columns, $G > N$ 1) ...
0
votes
2answers
21 views

whether the product of two symmetric matrix with one positive definite is diagonizable

Assume $A$ is symmetric and positive definite, $B$ is symmetric. Proof that $AB$ is diagonalizable and all the eigenvalues are real. I think it is better to write $A=R^TR$ and $B=XDX^{-1}$, but I ...