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

learn more… | top users | synonyms

1
vote
0answers
62 views

Meaning of singular Jacobian and workarounds to Newton's method

I'm currently working with Galerkin's method to solve differential equations and I have to retrieve unknown coefficients for the truncate expansion. This is just to set the background for why I need ...
1
vote
1answer
47 views

Derivative of $\|Ax-b\|_1$

Using least squares approximation $E^2 = \| Ax - b\|^2 = (a_1x - b_1)^2+...+(a_mx-b_m)^2$ The derivative of E^2 at the point $\hat{x}$ is zero if: $(a_1\hat{x}-b_1)a_1+...+(a_m\hat{x}-b_m)a_m=0$ ...
0
votes
1answer
37 views

vector space of natural numbers

I wonder, is it possible for the natural numbers (with zero) t be a vector space on SOME field? I understand why it cannot be over real numbers because of muliplication with negative scalar. BUT what ...
0
votes
0answers
10 views

Get stuck with some statements of convergence rate of the iteration method from “Iterative methods for sparse linear systems (2nd edition) ”

Here are the statements I get from the book and the two highlight parts are what I can not understand well. The questions are: Why we can conclude that $\rho=\rho(G)$ from"the above analysis"? ...
0
votes
0answers
24 views

Interpolation question about polinomials?

Let $f(x)=x^n$. show that for each $n$ distinct point $x_0,... x_n$ we have $f[x_0,...x_n]=0$ and $f[x_0,...,x_{n-1}]=\sum_{i=0}^{n-1}x_i$. also show that if $x_{i+1}-x_i$ is fixed for each $i\ge 0$ ...
1
vote
0answers
21 views

LU Decomposition for the solution of two linear systems

Let's say I have the following linear system: \begin{equation} \left[ \begin{array}{cccc} S&&L^{T}&&A^{T}&&0\\ L&&0&&0&&0\\ ...
0
votes
0answers
14 views

Applying perturbed matrix to unperturbed eigenvector

Suppose we've got a matrix $P$ and a perturbed version $\hat{P}=P+E.$ Given that $v$ is an eigenvector of $P$ with $Pv=0,$ I'd like to get as sharp a bound as possible on $\hat{P}v$ (in terms of ...
0
votes
1answer
32 views

convolution on 2 by 2 matrices

Let $m$ be a positive integer, and let $A_1,B_1 \in \operatorname{SL}(2,\mathbb{Z})$. Can one always find matrices $A_2,B_2 \in \operatorname{SL}(2,\mathbb{Z})$ such that $$ A_1 \left( ...
0
votes
0answers
151 views

Matlab project - Jacobi method for tridiagonal matrices…

I have to do a project in Matlab to my University and I don't quite understand what I should do. I was given script that solves systems of equations with Jacobi's method with given tolerance and ...
1
vote
2answers
45 views

A function to convert a vector to a number and vise versa?

Sorry in advance if I didn't choose the right tags for the question, I wasn't sure. So I'm a programmer and writing a saving/loading system for data. The way I was serializing (saving) vectors is via ...
0
votes
1answer
26 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
35 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
40 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
62 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
50 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
1answer
50 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
24 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
42 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
44 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
20 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
16 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
3answers
77 views

Is $\bigl\|\frac{vv^T}{v^Tv}\bigr\|=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
66 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
25 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
50 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
123 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
40 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
1answer
34 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
32 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
33 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
27 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
55 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
42 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
56 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
29 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
31 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
29 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
17 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
32 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
25 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
85 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
45 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
40 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
38 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 ...
1
vote
1answer
49 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
9 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 ...
1
vote
0answers
69 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
32 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
55 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
17 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). ...