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

learn more… | top users | synonyms

0
votes
0answers
25 views

QR Algorithm without Shifts (Trefethen and Bau)

A real symmetric matrix $A$ has eigenvalue 1 of multiplicity 8, while all the rest of the eigenvalues are $\leq 0.1$ in absolute value. Describe an algorithm for finding an orthonormal basis of the ...
0
votes
1answer
17 views

Enciphered Message with linear enciphering function.

My semester tests are coming up and as I was looking through past papers I came across this question. I was missing a lot during the beginning of the year and this was no doubt covered during my ...
4
votes
3answers
26 views

Divergence of fixed-point iteration for real starting values

Consider the linear system of equations $Ax = b$ with invertible $A\in \mathrm{GL}(n,\mathbb R)$ and $b\in\mathbb R^n$. For $A = M - N$ with invertible $M$ the solution $x_* = A^{-1}b$ is a fixed ...
2
votes
1answer
34 views

Weed out numerical artifacts from matrix inversion

I am working with the inverses to a set of large sparse matrices (in Matlab). A key indicator for my application is the number of non-zero entries in each row, and I recently discovered that I was ...
0
votes
0answers
10 views

Strictly diagonally dominant matrix -LU factorization

Let $A\in\mathbb{C^{n\times n}}$ be strictly diagonally dominant. I want to show that the LU factorizations with and without partial pivoting are the same for these matrices. For start, I created ...
0
votes
1answer
45 views

Why base vectors are 1 in length? [closed]

I can't really find any substantial reference in the math literature that justifies the fact that basis vectors are usually $\begin{bmatrix}1&0&0\end{bmatrix}$ or ...
2
votes
2answers
44 views

Is there a function in MATLAB that will estimate the initial condition from a set of data?

I was given a state-space model of a system and a list of outputs for t=0 to t=5, sampled every 0.1 seconds and asked to approximate the initial condition. Is there a function in MATLAB that will take ...
0
votes
0answers
11 views

Pairing Two Point Clouds

So I have two point clouds $X$ and $Y$ each with $N$ points in the familiar $\mathbb{R}^3$ euclidian 3D space. I then have an inter-point distance $d(\vec x_i,\vec y_j)$ which is zero if $\vec x_i$ is ...
1
vote
2answers
35 views

stuck with some parts of the proof about “ matrix is normal iff each of its eigenvectors is also an eigenvector of its transpose conjugate matrix”

When I read the book Iterative Methods for Sparse Linear Systems, Second Edition, I get stuck with the following proof. The yellow highlight parts are the positions I have trouble to understand. ...
2
votes
1answer
19 views

how to prove the relationship about spectral radius, numerical radius and matrix two norm?

When I read page 24 in Iterative Methods for Sparse Linear Systems, Second Edition, I can not understand the following statement: (My major is not math) Let $A$ be an n-square complex matrix with ...
0
votes
0answers
8 views

Relative Error with Respect to Frobenius Norm

I'm look at this tiny book called "Deblurring Images: Matrices, Spectra, and Filtering" by Hansen, Nagy, O'Leary. This is a self study, but I believe my question is broad enough so that it can be of ...
0
votes
0answers
9 views

Dimensionality Reduction

Let $X\in\mathbb{R}^{100\times 100}$ matrix and let its eigenvector and eigenvalues be $X_{vec}$ and $X_{val}$ respectively. If the rank of $X$ is $5$, then is it possible to approximate $X$ with ...
1
vote
2answers
41 views

Is $\biggl\|\frac{vv^T}{v^Tv}\biggr\|=1$? For any vector $v\in \mathbb{R}^{n}$

I am stuck while showing that $$\biggl\|\frac{vv^T}{v^Tv}\biggr\|=1,$$ where $v\in \mathbb{R}^n$, and $\|.\|$ is a matrix norm. Here is my steps: I used Frobenius norm: A Frobenius matrix ...
0
votes
1answer
35 views

How does the Simplex method of solving LPs use the starting solution?

Say one looks at the LP (in slack form) and sees that assigning $0$s to all the non-basic variables doesn't give a valid solution but some other non-trivial assignment of values to the non-basic ...
0
votes
2answers
17 views

What does it mean by one matrix is **unitarily similar** to another?

I am reading a tutorial about the Lanczos method for eigen problem / SVD. It mentioned "Then the tridiagonal matrix $B^∗B$ is unitarily similar to $A^∗A$. " What does it mean? I can derive this: ...
1
vote
1answer
19 views

conjugate gradient method for semi definite case

Show for a symmetric, positiv semi definite matrix $A$, a vector $b\in Ran(A)$ and initial vector $x_0$: (1) All directions $d_0,d_1,...,d_m$ of the conjugate gradient method are in the range ...
0
votes
2answers
35 views

Definition of Spectral Radius / Eigenvalues of Product of a Matrix and its Complex Conjugate Transpose

For any matrix $\textbf{A}$, I know that in the Euclidean L2 induced/operator norm, $\|\textbf{A}\|=\sqrt{\rho(\textbf{A}^{*}\textbf{A})}$, with * being the complex conjugate transpose and $\rho$ ...
0
votes
0answers
16 views

Condition number perturbation

I have a matrix of the form $\tilde{H} = H + i A A^\dagger$. It is known that $H$ is hermitian and that $\tilde{H}$ is invertible and $A A^\dagger$ has a kernel of dimension $\geq 1$. I want to study ...
-2
votes
0answers
39 views

Property Moore-Penrose inverse [closed]

Let $u \in \mathbb C^{m}$ and $v \in \mathbb C^n$ with $v \neq 0$. Show that $\| uv^{\dagger}\|_2 =\|u\|_2/\|v\|_2$ how I prove this? $v^{\dagger}=\frac{x^*}{\|v\|_2^2}$ so, ...
0
votes
0answers
22 views

Householder reflector sign error

I am studying Householder reflectors from Trefethen and Bau but am having trouble creating a simple example for it. I am given the equation for the vector v that the Householder reflector H is based ...
2
votes
1answer
31 views

Finding An Orthogonal Matrix

Let $u = (0,1,2,2)^{T}$, $v = (-3,0,0,0)^{T}$. Find an orthogonal matrix $A$ such that $Au=v$ and $A = I-B$, where $B$ is a matrix of rank one. I started by writing $A$ as $A = I - xy^{*}$ and using ...
0
votes
0answers
16 views

Computing a few eigenvalues of large sparse nonsymmetric matrix without LU factorisation

I'm trying to find a few targeted eigenvalues of a large sparse (N=1e6,nnz=4e6) non-symmetric matrix. Currently I'm using MATLAB's 'eigs' function with the 'sigma' option and this uses the Shifted ...
0
votes
1answer
17 views

Psuedo-inverse of block low-rank, symmetric matrix?

I have a matrix that looks like $$ D = \left[ \begin{matrix} c_1aa^T & c_2ab^T \\ c_2ba^T & c_3bb^T \end{matrix} \right] $$ where $c_1, c_2, c_3$ are scalars and $a, b$ ...
1
vote
0answers
14 views

the Gauss-Jordan algorithm requires how many multiplications/divisions and add/subtractions

I am trying to show this following result. The Gauss-Jordan algorithm requires $\frac{n^3}{2}+n^2-\frac{n}{2}$ multiplications/divisions and requires $\frac{n^3}{2}-\frac{n}{2}$ ...
2
votes
1answer
38 views

derivation of GMRES question: why is my result for the approximate solution to $Ax=b$ always exact?

I am trying to see if I understand the GMRES method and it's result. But somewhere I get confused and I wonder if I am making a mistake. We start with a system $Ax=b$. We look for approximate ...
0
votes
1answer
35 views

Rank of the evaluation of a polynomial matrix

Given a polynomial matrix $A(t)$ of rank $r$, I would like to know at what complex evaluations of $t$ the rank decreases. Some research with google told me these values are sometimes called the zeros ...
1
vote
1answer
52 views

Connection between results of two SVDs

Consider SVD of $M$: $$ M = U \Sigma V^\top $$ And SVD of $N= \ln M$: $$ N = U^\prime \Sigma^\prime V^{^\prime\top} $$ Anyone knows/has seen/can think of any interesting connection/relation between ...
0
votes
0answers
10 views

SOR and Conjugate Gradient Method

Let $H_n=[H_{ij}]\in\mathbb{R}^{n\times n}$ be Hilbert Matrix, define $h_{ij}=\frac{1}{i+j-1}$ and $x=\left(1\quad 1\quad\cdots\quad 1\right)\in\mathbb{R}^{n\times n}$ such that $b_n=H_nx$. Use SOR ...
0
votes
0answers
17 views

Recasting Ax=b to use SOR method

Just need some guidance as to how to recast the matrix equation equation $Ax = b$ so that I can produce an iterative matrix to perform Succesive Over Relaxation on. These matrices are $n x n$ I ...
3
votes
1answer
27 views

Is this a reasonable method of numerically comparing two matrix functions?

I am currently trying to compare two matrices with elements which are too complicated for me to algebraically show that they are equal element wise and I decided to try the following approach: ...
2
votes
0answers
23 views

Can the Lanczos algorithm converge very fast by taking a good initial guess?

Suppose I have the two lowest eigenvectors $v_1$, $v_2$ of a matrix $M$. If slightly change $M$ to $M'$. Can I use $v_1$ or $v_2$ as an initial guess for $M'$? If so, which one should be used, $v_1$ ...
0
votes
0answers
12 views

Properties of specific case of the gradient descent method

Consider the gradient descent method for the system $Ax=b$ where, $A=\begin{pmatrix}1 & 0 \\0 & a\end{pmatrix}, b=\begin{pmatrix}0 \\ 0\end{pmatrix}$ and the initial vector ...
0
votes
1answer
22 views

Why outer product isn't backward stable

Outter product isn't backward stable. This is because output matrix most likely has rank one and thus can't be represented in the form $(x + \delta x)(y + \delta y)^*.$ Also we know that if output ...
0
votes
3answers
15 views

Matrix Norm Division

Suppose $A=uv^*$ where $u$ is an $m$-vector and $v$ is an $n$-vector. For any $n$- vector $x$, we can bound $||Ax||_2$ as follows: $||Ax||_2 = ||uv^*x||_2=||u||_2|v^*x|\leq||u_2||||v||_2||x||_2$. ...
0
votes
1answer
67 views

Solve Bratu problem using Python

I am going crazy trying to solve the Bratu problem using Python: $$y''(x)+ e^{y(x)} = 0, \quad \lambda = 1, \quad x \in(0,1),$$ $$y(0) = y(1) = 0$$ I have to solve this using the tridiagonal ...
0
votes
1answer
27 views

Uniqueness of Thin QR Factorization.

Let $A \in \mathbb C^{m x n}$, have linearly independent columns. Show: If $A=QR$, where $Q \in \mathbb C^{m x n}$ satisfies $Q^*Q=I_n$ and $R$ is upper triangular with positive diagonal elements, ...
2
votes
2answers
38 views

How to show that $\| QA\|_2=\| A \|_2$ where $Q$ is unitary (for a matrix A)

I want to show that for a unitary matrix $Q$ and a matrix $A$ that $$ \|QA\|_2=\|A\|_2$$ I start with the definition of matrix induced norms: $$\| QA \|_2 = \sup_{x \neq ...
0
votes
1answer
23 views

What is the computational cost of reduced row echelon and finding the null space?

I'm taking computational linear algebra, and haven't been able to find too much information about the computational cost (in terms of m=rows and n=cols) of these two routines: Reduced Row Echelon ...
0
votes
1answer
33 views

The equivalence of numerical radius and spectral norm

Let $A$ be a $n\times n$ complex matrix. Define the numerical norm of $A$ as $$w(A)=\sup\{|x^*Ax|;\|x\|_2=1\}, \|x\|_2^2=\sum_{i=1}^n|x_i|^2.$$ And the spectral norm of $A$ is $$\|A\|_\infty ...
0
votes
1answer
8 views

What is and what represents a convergents function in polynomial form?

$$\mathbf{convergents}(cos(1), 20)$$ What exactly is a convergents function and what, that series of fractions is representing ? There is an use for this in numerical linear algebra ? Feel free to ...
0
votes
0answers
30 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 ...
0
votes
2answers
21 views

Creating a random square matrix with known singular values

The first step in one question has me creating a random square matrix A with singular values given as $2^{-1}, 2^{-2}\dots 2^{-n}$. There is no other information about what assumptions can be made ...
1
vote
0answers
49 views

Does this function have a unique fixed point?

Consider the following equations in fixed-point form: $$\mathbf{x}=F(\mathbf{x})=[f_1(\mathbf{x}),f_2(\mathbf{x}),\cdots,f_n(\mathbf{x})]^T$$ where the function $f_i$ is defined as ...
1
vote
0answers
13 views

Speed of pseudo-inverse (with possibly ill-conditioned matrices)

I am computing the pseudo-inverse of several matrices of identical size $m \times n$ . However, computation (e.g. with the LAPACK pinv) seems to be much slower in some cases (5 to 10 times slower). ...
-2
votes
1answer
63 views

Invent a linear mapping given the following conditions. [closed]

Invent a linear mapping L such that: $L(1,2)=(3,5)$ and $L(-2,1)=(2,-3)$ I'm just unsure on how to start this problem, if anyone can give me any tips that be great thanks!
0
votes
1answer
25 views

An Inequality in Numerical Optimization

I am reading Jorge Nocedal and Sepher J. Wright's Numerical Optimization and stuck at an exercise 4.6 in chapter 4. The Canchy-Schwarz inequality states that for any vector $u$ and $v$, we have ...
2
votes
1answer
50 views

about the power of a matrix

Assume that matrix $A$ contains only 0 or 1 elements. Could anyone give me some condition, under which the matrices $A^i$ (for $i=1,2,3,...,k$) still contains only 0 or 1 elements. For example, I ...
1
vote
1answer
59 views

Solve quadric equation system

How to solve this? For given real and symetric matrices $A_1,A_2,A_3,A_4\in\mathbb{R}^{4\times4}$ find $x\in\mathbb{R}^4$ $$x^TA_1x=0$$ $$x^TA_2x=0$$ $$x^TA_3x=0$$ $$x^TA_4x=0$$
8
votes
2answers
277 views

Interpolation polynomial Challenge

suppose $p(x)=x^k-x^t, k \neq t $ (k,t is a positive integer). function q(x) be a Interpolation polynomial from degree lower or equal n, to data $i=1,...,n+1, (x_i ,p(x_i))$. if ----------- then ...
1
vote
0answers
29 views

Strictly diagonal matrix

Suppose that matrix $A$ is strictly diagonally dominant, show that $||A^{-1}||_{\infty}\leq[min(|a_{ii}|-|\sum_{i\neq j}^n a_{ij}|)]^{-1}$.