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

learn more… | top users | synonyms

2
votes
1answer
78 views

Eigenvectors of transition matrices in PageRank algorithm

In my probability course, we were discussing applications of Markov Chains to computer science -- in particular, how the PageRank algorithm goes about finding stationary distributions, and thus, ranks ...
0
votes
2answers
1k views

How to solve $Ax=b$ via backward and forward substitution on Matlab

How can I solve $Ax=b$ in Matlab code via LU factorization. I know that the command [L,U]=LU(A) stores the ...
2
votes
0answers
45 views

Wiedemann for solving sparse linear equation

I am new member. I am researching in Wiedemann algorithm to find solution $x$ of $$Ax=b$$ Firstly, I will show a Wiedemann's deterministic algorithm (Algorithm 2 in paper Compute $A^ib$ for ...
0
votes
1answer
94 views

help to find SOR optimal parameter $w$

Please let following linear system as $Ax=b$: $$\begin{array}{l} 6a{x_1} + {x_2} + {x_3} = 1\\ {x_1} - 3a{x_2} + 4{x_3} = 2\\ {x_1} + {x_2} - 2a{x_3} = 3 \end{array}$$ Help me to prove that the ...
0
votes
0answers
62 views

Induced matrix p-norm

Let $\|\cdot\|_p$ denote the $p$ norm $(p≥1)$ defined for every vector $x=(x_1,x_2,\ldots,x_n)^t\in\mathbb C^n$ by $\|x\|_p=(\sum|x_j|^p)^{1/p}$ and let $|||\cdot|||_p$ denote the matrix norm defined ...
1
vote
0answers
45 views

What's the point of 1-norm matrix estimation? Why not brute force?

Calculating (brute-force) 1-norm of a square matrix should take $O(n^2)$ operations, with a small factor involved. Apparently, there is an algorithm (link) for estimating 1-norm that takes $O(n^2 t)$ ...
3
votes
2answers
78 views

Calculating the determinant of $A$ with $A_{ij}=a$ for $i<j$, $A_{ij}=-a$ for $i>j$, $A_{ii}=x$, using a pen and paper

Let $$A = \left[\begin{array}{cccccc} x&a&a&a&\dotsm&a\\ -a&x&a&a&\dotsm&a\\ -a&-a&x&a&\dotsm&a\\ -a&-a&-a&x&\dotsm&a\\ ...
0
votes
1answer
66 views

Finding the minimum of Condition number for this matrix

Suppose $A=\left[ {\begin{array}{*{20}{c}} {0.1\alpha }&{0.1\alpha }\\ 1&{1.5} \end{array}} \right]$. How can we find minimum of condition number $k(A)=\Vert A\Vert \Vert A^{-1} \Vert$ (Assume ...
1
vote
0answers
36 views

Is it better to compute $A^tA$ once and then $Ax$ several times or compute $y=Ax$ and then $A^ty$ every time?

So I have this algorithm which given a matrix $A$ it assigns $A=A^tA$ outside the loop and then on the algorithm loop it solves multiple instances of $Ax$ for different $x$s, (meaning that it's ...
3
votes
2answers
126 views

Good Textbook in Numerical PDEs?

I am currently taking a course on Numerical PDE. The course covers the following topics listed below. Chapter 1: Solutions to Partial Dierential Equations: Chapter 2: Introduction to Finite ...
2
votes
1answer
55 views

Restoring matrix from covariance matrix

Given $ A^TA $, how to restore $A$? (Any $A$ which produces this $ A^TA $). Given matrix $ A^TA $, vector $b$, and vector $Ab$, how to restore a matrix $A$ ? Correction to 2: The vector $A^Tb$, ...
0
votes
1answer
59 views

Why won't my conjugate gradient algorithm work?

I made this simple Conjugate Algorithm on Matlab n = length(b); r0 = b - A*x0; p0=r0; k=1; n0=(r0')*r0; while n0 >= eps && k <= n ...
0
votes
0answers
253 views

update cholesky factorization

I need to compute the Cholesky factorization of $H'H$ where $H$ is a big sparse rectangular matrix. After that $H$ is modified by adding several lines. That is H_n = [H ; line_1 ; ... ; line_n] in ...
1
vote
0answers
53 views

matrix with positive diagonal elements

I was wondering if a symmetric matrix with positive elements only in the diagonal (negative elsewhere) is any special beside the symmetry. Thanks in advance
2
votes
0answers
56 views

Find the solution of linear equation using Wiedemann/ Krylov method

I am using Wiedemann (some literature called Krylov method) to find the solution of a linear equation that defined as $$Mx=b$$ Instead of resolving entire elements of x (size $K \times 1$), we can ...
1
vote
1answer
22 views

If normal linear regression finds $A$ such that $AX \sim Y$, then how do I solve $BAX \sim Y$?

If normal linear regression finds $A$ such that $$AX \sim Y$$ then how should I solve $$BAX \sim Y$$ where $B$, $X$ and $Y$ are given (non-invertible) matrices? I could of course derive the solution ...
0
votes
1answer
87 views

Eigenvalue inequalities for Hermitian matrices

This is a problem from Horn and Johnson's Matrix Analysis. I've tried to follow the problem but I can't find a way to lead to the conclusion the problem is suggesting. Any solutions, hints, or ...
0
votes
1answer
18 views

A problem about a theorem on irreducible matrix

I'm stuck on a problem where I need to find a counterexample. I'm not sure how to come up with a reducible matrix to show that it doesn't satisfy the result of the following corollary. Any solutions, ...
0
votes
1answer
23 views

Suppose that $A \in M_n$ is strictly diagonally dominant. Show that $|a_{kk}|$ $\lt C_k'$, for at least one value of $k$

Suppose that $A \in M_n$ is strictly diagonally dominant. Show that $|a_{kk}|$$\gt C_k'$, for at least one value of $k=1,\dots, n$, where $C_k'$ denotes $A$'s deleted absolute column sums ($a_{kk}$ is ...
2
votes
1answer
62 views

Suppose that the $n$ Gersgorin discs of $A \in M_n$ are mutually disjoint. If $A$ is real, show that every eigenvalue of $A$ is real.

Suppose that the $n$ Gersgorin discs of $A \in M_n$ are mutually disjoint. (a) If $A$ is real, show that every eigenvalue of $A$ is real. (b) If $A \in M_n$ has real main diagonal entries and its ...
2
votes
1answer
36 views

Show that the intersection taken over the Gersgorin discs of all similar matrices of $A$ $=$ $\sigma (A)$

Show that $\bigcap_S G(S^{-1}AS)$ $=$ $\sigma (A)$; the intersection is taken over all nonsingular $S$, and $\sigma (A)$ is the spectrum of $A$. I'm lost as how to even begin to prove this fact. Any ...
1
vote
2answers
40 views

Domain for which this matrix is positive definite

What is the domain for which this matrix is positive definite? $$\left(\begin{array}{cc} 12x^2 & 1 \\ 1 & 2 \\ \end{array}\right)$$ I'm trying to figure this out. I know the ...
1
vote
0answers
70 views

Rayleigh quotient ($|r(q)-\lambda|=O(||q-x||_2^2)$ ?)

how to show $|r(q)-\lambda|=O(||q-x||_2^2)$ $r(q)=q^*Aq/(q^*q)$ and $\lambda$ is an eigenvalue, A is a Hermitian matrix. x is the unit eigenvector corresponding to $\lambda$. and q is a unit vector. ...
0
votes
1answer
78 views

Interpolation of polynomials

let $f(x)=2^x$ and $x_0=1$, $x_1=2$, $x_2=3$. Use divided differences to compute the interpolation polynomial $P(x)$ satisfying $P(x_i)=f(x_i)$, i=0,1,2 and $P'(x_1)=f'(x_1)$ and estimate error ...
0
votes
0answers
43 views

Is the following matrix Upper Hessenberg?

Does $$ A = \begin{pmatrix} 1 & 1 \\ -1 & -1 \end{pmatrix}$$ properly satisfy the definition of upper Hessenberg?
0
votes
0answers
43 views

Show that Newton’s Method is well-defined for all k and converges to 0 for $x_0>0$

Let $f : R → R$ with $f$ twice continuously differentiable, $\gamma > f''(x)>\delta, f(0)=0,f'(x)>\rho $ for $x ≥ 0$. Show that for any $x_0 > 0$ that Newton’s Method is well-defined for ...
0
votes
1answer
31 views

Generalized Eigensystems

I am looking for solution algorithms for a second order generalization of the eigenvalue problem. A, B, and C are n-by-n matrices, I is the n-dimensional identity matrix, $\lambda_i$ is an unknown ...
0
votes
0answers
29 views

Jacobi Iteration with Shift

The question is to solve a linear system using Jacobi iterations with a shift of mu = 5. My code converges very quickly, but it does not yield the results that MATLAB gives with the backslash ...
1
vote
0answers
231 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
51 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
62 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 ...
1
vote
0answers
25 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
29 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
34 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
314 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
70 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
48 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
46 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
44 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
1answer
54 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
57 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
35 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
52 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
213 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
50 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
1answer
27 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
82 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
106 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
40 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: ...
2
votes
1answer
171 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 ...