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

learn more… | top users | synonyms

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
188 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
46 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
27 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
37 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
69 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
52 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
51 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
50 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
24 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
18 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
68 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
26 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
62 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
151 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
44 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
34 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
34 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
42 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
64 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
43 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
31 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
31 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
34 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
26 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
89 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
48 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
41 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
42 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
51 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
85 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
58 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
20 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). ...
0
votes
1answer
29 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
54 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
75 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$$
1
vote
2answers
294 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 ...
2
votes
1answer
49 views

Strictly diagonal matrix

Suppose that matrix $A$ is strictly diagonally dominant, show that $$\|A^{-1}\|_{\infty}\leq\left[\min_i\left(|a_{ii}|-\left|\sum_{\substack{j\neq i}} a_{ij}\right|\right)\right]^{-1}.$$
1
vote
1answer
92 views

Condition number - proof

I have a problem with which I've been struggling for a while. It's probably not that difficult, but I seem to be stuck so... here we are. Let A be an invertible lower- or upper-triangular matrix ...
1
vote
0answers
57 views

Saddle point problem (KKT) with block-diagonal matrix

Consider the following saddle point problem originating from an interior-point method algorithm: $$ \begin{bmatrix}\mathbf{H} & \mathbf{A}^{T}\\ \mathbf{A} & \mathbf{0} ...