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

learn more… | top users | synonyms

0
votes
0answers
28 views

LU Decomposition simplification on a tridiagonal matrix

If I have a tridiagonal matrix that looks like Tn = diag[1, 3, 1], I can do LU Decomposition of it using n - 1 multiplications (by omitting multiplications with 1) but not n - 1 divisions, right? In ...
0
votes
0answers
22 views

A problem about the condition number

Given that $I\in R^{n\times n}$ is identity matrix and $||I||=1$.Assumed that Matrix $A\in R^{n\times n}$ is nonsingular,with $\delta A$ satisfying $||A^{-1}||||\delta A||<1$. Then $A+\delta A$ is ...
2
votes
1answer
23 views

Issue with trigonometry identity related to condition number of matrix

So, in attempting to compute the condition number for the 2-norm of a matrix, I have stumbled upon a problem i can't resolve. I have the formula $$ \frac{1-\cos\left(\frac{n}{n+1} ...
3
votes
1answer
41 views

partition of block matrices

If $A=\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \\ \end{bmatrix}$ is a partition of $A$ such that $A_{11}$ and $A_{22}$ are $r × r$ and $(n − r) × (n − r)$ ...
0
votes
2answers
39 views

Show that n(n+1)/2 multiplications are required

$a_{11}x_1$+$a_{12}x_2$+$a_{13}x_3$+ ...+ $a_{1,n-1}x_{n-1}$+$a_{1n}x_n$ =$b_1$ $a_{22}x_2$+$a_{23}x_3$+ ...+ $a_{2,n-1}x_{n-1}$+$a_{2n}x_n$ =$b_2$ $a_{33}x_3$+ ...+ $a_{3,n-1}x_{n-1}$+$a_{3n}x_n$ ...
0
votes
0answers
17 views

Question related to matrix transformation in sequence spaces.

Let $M=[K_{i,j}]$ be an infinite matrix, where $K_{ij}=1/i \text{ if } 1\leq i \leq j \text{ and } K_{ij}=0 \text{ if } i>j\geq 1$. Then $M$ defines a map $\ell^p \to \ell^r$ iff $p=1 \text{ and } ...
0
votes
0answers
14 views

convergnece of QR-method

I'm studying the QR-algorithm. In particular I have this algorithm: For every $k=0..n $ select a shift $\sigma_k$ factorize $A_k-\sigma_k I =Q_kR_k$ multiply $A_{k+1}=R_k Q_k+\sigma_kI$ muliply ...
0
votes
1answer
57 views

Guaranteeing Invertibility with Banach Lemma

I'm trying to find an $\epsilon$ for which the Banach Lemma guarantees $I_n + ɛA_n$ is Invertible, where $A_n$ is a matrix of $1$'s, and $I_n$ is the identity matrix, and $n$ can be any dimension. ...
1
vote
1answer
101 views

Prove that Q is also upper Hessenberg in A = QR

Background: Suppose $\mathbf{A}$ is an $n \times n$ matrix and it is upper Hessenberg. Using QR-factorization, we have $\mathbf{A=QR}$, where $\mathbf{R}$ is an upper triangular matrix and ...
1
vote
0answers
217 views

GAXPY Operations

Let A ∈$R^2$, x ∈ $R^k$. Find the first column of M = (A − x1I)(A − x2I)...(A − xkI) using a sequence of GAXPY’s operations. GAXPY: General matrix A multiplied by a vector X plus a vector Y. I tried ...
0
votes
0answers
45 views

Compression of a matrix A by V

I can't understand and even can't find any text on Compression of a matrix A by V. meaning if $B=V^*AV$ then B is called the compression of A. What does it mean???
1
vote
1answer
41 views

Householder reflection

Let $\tau \in \mathbb C$, $x,y,v \in \mathbb C^n$. I have to show that if i) $|\tau| =\frac{ \|x \|_2}{\|y\|_2}$, ii) $\tau x^H y \in \mathbb R $ iii) $ \rho( x-\tau y)=v$ with ...
1
vote
2answers
47 views

Inverse of a block matrix with particular entries

Good afternoon; I have the following block matrix: $X$ = $$\pmatrix{U&M\\M&V}$$ Where $U,V,M$ are square matrices of size $n\times n $, and it holds: $U^2 = V^2 = M^2 = I$ ; with $I$: ...
1
vote
3answers
66 views

Matrix Norm Proofs: Dropping the “max” term and denominator

To prove that $||A||_{\infty}≤\sqrt{n}||A||_{2}$, this math.exchange proof does the following: $$||A(x)||_{\infty}≤ ||A(x)||_{2}≤||A||_{2}||x||_{2}≤||A||_{2}\sqrt{n}||x||_{\infty}$$ Given the ...
0
votes
0answers
41 views

Solving for intersection of line and a vector function.

How would one approach a problem of finding intersection points between a line $\vec l = \vec S + d \vec t$ and vector of the form $$\vec v = \begin{pmatrix} x \\ y \\f(x, y) \end{pmatrix}$$ I am ...
2
votes
1answer
46 views

Solving a complex, sparse, linear system using the Schur-complement

Solution method I am repetitively solving sparse linear systems (for the need of ARNOLDI iterations) of the type: $$\underbrace{\begin{bmatrix} J_1 & J_2 \\ J_3 & J_4 \end{bmatrix}}_J ...
0
votes
1answer
48 views

Does an orthonormal matrix preserve the $p$-norm?

Let $\,A\,$ be a $\,n \times k\, $ matrix, and $\,B\,$ a $\,k \times n \,$ be an orthonormal matrix. Is it true that $\,\left\|AB\right\|_p = \left\|A\right\|_p\,$ for every $\,p\neq 2$?
1
vote
0answers
29 views

Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include: All vectors in $S$ All vectors in $T$ All vectors that can be ...
0
votes
1answer
75 views

Algorithms for computing matrix logarithm.

On my quest to find the holy grail of mathematics become a little bit better at algebra, I have read up on matrix logarithms and exponentials and how useful they can be in investigating groups and ...
0
votes
1answer
39 views

Equaity of two norms of matrix

I have to prove that if A is a $n \times k $ matrix and $A^H$ the hermitian matrix of A, $||A||_2=||A^H||_2$. Where $||A||_2=\sup\{ ||Ax||: ||x||\leq 1\}$ and $|| \cdot ||$ is the euclidean nrmm of ...
2
votes
1answer
43 views

equality of norms

I have to show that $\| A\|_2=\sqrt{\| A^H\times A\|_2}$. $A$ is a $n\times k$ matrix, $\| \cdot \|_2$ is defined as : $$\| A\|_2=\sup\{ \|Ax\|, \|x\|\leq 1 \}$$ and $\| \cdot \|$ is the ...
0
votes
2answers
35 views

A proof of the uniqueness of svd?

I understand the geometric intuition, but the proof by induction in Trefethen book confuses me : it seems to me that a 1*1 complex matrix has infinitely many left and right singular vector pairs? ...
1
vote
0answers
38 views

Computational methods to minimizing the norm of a matrix monomial.

Linear optimization solves the problem $$\min_{\bf x}\{\|{\bf Ax - b}\|_2^2\}$$ Edit: Some clarification Doing the derivation of the optimum, first expand the norm: $$\|{\bf Ax - b}\|_2^2 = ({\bf ...
0
votes
0answers
37 views

Rapid calculation of eigenvectors for a submatrix when I know the eigenvectors of the full matrix

I have an $N \times N$ matrix $Z$ that is complex-valued and nonsymmetric in general. I can solve for the eigenvalues and eigenvectors of this matrix numerically. Call the diagonal eigenvalue matrix ...
2
votes
1answer
62 views

To create a special matrix !!

How to create a $N \times N$ matrix with $1$ and $-1$ as its elements, such that when this matrix is multiplied with its transpose the resultant matrice is $N \times \mathbb{I}_N$. Where $N$ is a ...
0
votes
0answers
70 views

Extracting I-Vectors from a GMM-supervector

The probability model for I-vector in GMM-UBM system is : M = M(ubm) + Ty where, M is GMM supervector (means of all gaussian components concatenated in single vector) M(ubm) is UBM supervector I ...
0
votes
1answer
47 views

How to substitute and matrix into a functions?

I have $f(x)=2*x_1 +x_2$ how to find $f(m*x)$ if m is a matrix $m=\begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix}$
0
votes
0answers
10 views

Response Matrix with finit actuator

I have a system of penalties ($P$) and actuators($A$). Whereby: d$P_i/$d$A_j$ = close to constant $\quad\forall i,j$ In order to minimize $P$, I create a response Matrix ($M$). With its ...
0
votes
0answers
48 views

Looking for references on the complexity of computation of a basis transformation matrix

I'm looking for some references on the complexity for the following kind of problem: Given two Basis $(a_1, ... ,a_n)$ and $(b_1, ..., b_n)$ of the $K(x)$-vector space $V$ I want to compute the ...
0
votes
0answers
23 views

Speeding up Conjugate Gradients iterations for Sparse Matrices?

I've been using Conjugate Gradients to minimize linear systems involving sparse matrices. Although many of my sparse matrices are highly specialized - i.e. for any given row it is easy to know which ...
0
votes
0answers
46 views

Finite difference: Radial symmetry boundary condition in tridiagonal system?

I am putting together an axisymmetric finite difference solver for Poisson's equation over a non-"rectangular" boundary in axisymmetric cylindrical coordinates. I was planning on using the dynamic ...
0
votes
0answers
33 views

Error bounds for solution of system of linear equations when coefficients are uncertain

I have a square system $Ax=b$ and would like to know how much the solution $x$ can change when I change the coefficient matrix $A$. I've stumbled upon the condition number, but this seems to apply ...
4
votes
1answer
69 views

What mathematics topics pertain more towards applied mathematics?

I'm entering my second year of undergrad (majoring in mathematics), and I've found that I am really bad at Linear Algebra, but very good at Calculus and Differential Equations. I'm hoping to venture ...
0
votes
1answer
47 views

solve nonlinear system of equation numerically

solve the following system of equations numerically $$2x+2y - e^{xy} = 0$$ $$x^3 + y - xy^3 = 1$$ I'm also asked to solve analytically but I'm pretty sure the closed form solution doesn't exist ...
1
vote
1answer
42 views

Improving the performance of eigs for a large spd Problem

I have two large (think around $100.000\times 100.000$), sparse, real symmetric and positive definite matrices $A$ and $B$ and I want to find the smallest generalized eigenvalue $$Ax = \lambda_{\min} ...
2
votes
0answers
629 views

Number of Arithmetic Operations in Gaussian-elimination/Gauss-Jordan Hybrid Method for Solving Linear Systems

I am stucked at this problem from the book Numerical Analysis 8-th Edition (Burden) (Exercise 6.1.16) : Consider the following Gaussian-elimination/Gauss-Jordan hybrid method for solving linear ...
0
votes
1answer
32 views

Stability of (floating point) computed variance

Homework Question from Accuracy and Stability of Numerical Algorithms, 2nd Edition, by Nicholas J. Higham, page 33: So every time we store an number and do a operation, we introduce an error bounded ...
0
votes
0answers
28 views

What are some possible reasons for a large condition number?

For this question, please assume that I am talking about the condition number with respect to the spectral norm. That is, $\kappa_2(A) = \|A\|_2\|A^{-1}\|_2 = \frac{\sigma_{max}(A)}{\sigma_{min}(A)}$. ...
0
votes
0answers
12 views

Proof of QR Algoirthm Convergence

I am reading Trefthen and Bau and the amount of implicit proof steps are killing me. Can someone explain how the statement of convergence for the "pure" QR Eigenvalue Algorithm (Theorem 28.1) is ...
0
votes
0answers
22 views

how to project optimal parameters on to feasible region

Hi: I'm trying to understand the concept of projection and I created a toy example that might help me to do that. Suppose that I have a non-linear optimization with 3 parameters theta_1, theta_2 and ...
0
votes
0answers
37 views

Parametrization of the $Ax=b, x \geq 0$ domain for Monte-Carlo simulation

I have a linear system, $n=15$, with $6$ constraints. There's no problem finding a single solution or establishing the null space; so I can see the full solution space. But I'm only interested in ...
0
votes
0answers
12 views

Linear Relationship of two equations

if $0.46a = 120b$ and $2.68a = 60b$ The relationship is linear. what does $0b$ equal in terms of $a$? what does $1b$ equal in terms of $a$? A method to work this out would also be nice, I have ...
1
vote
1answer
28 views

Gauss Seidel Iteration for a specific matrix

We seek to solve $Au= f$ via iteration, where $$ A = \left ( \begin{array}{cc} I & S \\ -S^T & I \end{array} \right ) $$ Where $S$ is an arbitrary square matrix in $R^n$ and $I$ is the ...
4
votes
1answer
63 views

LU decomposition for cyclic tridiagonal matrices

It is known that a tridiagonal matrix $$ A = \begin{pmatrix} b_1 & c_1 & 0 & 0 & \dots & 0\\ a_2 & b_2 & c_2 & 0 & \dots & 0\\ 0 & a_3 & b_3 & c_3 ...
1
vote
0answers
42 views

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $?

How can I write $\prod\limits_{i = 0}^n {\left( {x - {x_i}} \right)} $ in terms of a polynomial as $\sum\limits_{i = 1}^n {{a_i}{x^n}} $? In the other words, is there a way to write $a_i$ in terms of ...
0
votes
0answers
74 views

Most stable algorithm to solve a system of linear equations?

I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to ...
1
vote
1answer
50 views

Strange behavior with coordinate transformation of square and quadrilateral

I am trying to map coordinates from a quadrilateral to a square. The coordinates are square: $(500,900)(599,900)(599,999)(500,999)$ quad: $(454,945)(558,951)(598,999)(499,999)$ where the $i^{th}$ ...
0
votes
1answer
32 views

Notation regarding linearization near equilibrium point of dynamical system

Suppose we have $\frac{dx}{dt} = \dot{x} = f(x)$ with equilibrium point $x_e$ such that $f(x_e) = 0$. Then for the linearized approximation of the differential equation near $x_e$ we hope to use the ...
1
vote
1answer
54 views

How to determine positive or negative definite of a bordered Hessian ?

I want to determine the minimization result I get using Lagrange Multiplier method is a local minimum by determining whether the Bordered Hessian is positive definite or negative definite.(Hopefully ...
0
votes
1answer
56 views

Bound on the difference of matrix diagonals

I have two diagonal matrices $\Lambda,\hat{\Lambda}\in\mathbb{R}^{n\times n}$ with non-negative diagonal elements. And I have two matrices $W,\hat{W}\in\mathbb{R}^{m\times n}$, with $m\geq n$, each ...