With column vectors, entry $P_{ij}$ is the fraction moving from region $j$ to region $i$. The first column is therefore $(1/2,1/4,1/4{)}^{\mathsf{T}}$, the second is $(1/2,1/2,0{)}^{\mathsf{T}}$, and the third is $(1/2,0,1/2{)}^{\mathsf{T}}$. HenceEach column sums to one, as required for this convention for a stochastic matrix. Multiplying by $P$ conserves the total resources.

The reduced row echelon form givesChoose the free variables $x_3=s,x_4=t$. ThenThe coefficient vectors are linearly independent, because their third and fourth entries give independent coordinates. ConsequentlySubstitution in the original matrix verifies $Ax=0$ for both basis vectors. The rank-nullity theorem supplies the independent dimension check $2+2=4$.

The pivot columns in the row echelon form are columns 1 and 2. Take the corresponding columns of the original matrix:For a direct check, call these columns $c_1,c_2$. The other columns satisfy $c_3=c_1-c_2$ and $c_4=c_1+c_2$, so they are in the same linear span. Also $c_1,c_2$ are linearly independent: their fourth entries force the coefficient of $c_2$ to vanish, then their first entries force the other coefficient to vanish. Elementary row operations preserve dependence relations among columns, but generally change the column space itself, which is why the original columns must be used.

Use Gaussian elimination. Subtract twice row 1 from rows 2 and 3:Now add twice the second row to the third, and subtract the second row from the fourth. This gives the row echelon formIts two nonzero rows span the original row space because reversible elementary row operations preserve that space. They are linearly independent, as witnessed by their leading entries in different columns. ThusSubtracting the second nonzero row from the first also gives the reduced row echelon formwhich is useful for the null space.

If $x\in \mathrm{Null}(A)$, the $i$th entry of $Ax=0$ says $r_i\cdot x=0$. Any $y\in \mathrm{Row}(A)$ is a linear combination $y={\sum }_i{\alpha }_i{r}_i$, so bilinearity of the dot product givesHenceThis proves the orthogonality for every pair of vectors in the two vector subspaces. In fact the null space equals the orthogonal complement of the row space, since being orthogonal to every row is exactly the system $Ax=0$.

For an $m\times n$ matrix $A$ over the real numbers, write its rows as $r_1,\dots ,r_m$ and its columns as $c_1,\dots ,c_n$. ThenThus the row space and column space consist of all linear combinations of the corresponding rows and columns; the null space is the kernel of a linear map represented by $A$. The matrix rank counts independent row or column directions, with row rank equal to column rank.

The elementary row operations preserve the determinant, and the diagonal product of the upper triangular matrix found above isConsequentlyAt $t=1$, all four rows are equal. At $t=-1$, successive rows alternate between one row and its negative. In either case the matrix rank is one, confirming the vanishing determinant.

Perform the elementary row operations from the bottom upwards:This order matters because each subtraction uses the predecessor's original row. For example,The other two differences are $(0,0,1-t^2,t-t^3)$ and $(0,1-t^2,t-t^3,t^2-t^4)$. Thus the required upper triangular matrix isThese elementary row operations use no division, so the reduction remains valid for all real numbers $t$, including $t=\pm 1$.

For $i\ne j$, the elementary row operation $R_i\leftarrow R_i-k{R}_j$ leaves the determinant unchanged:By multilinearity in row $i$, the left side is $\det A$ minus $k$ times a determinant with row $j$ appearing twice. That second determinant is zero by alternation. No row scaling or row interchange is involved.

For either an upper triangular matrix or a lower triangular matrix,In the permutation formula for the determinant, every contribution except the diagonal product includes an entry on the zero side of the diagonal. Equivalently, successive cofactor expansions along the first column of an upper triangular matrix prove the formula by mathematical induction.

Apply the elementary row operation $R_1\leftarrow R_1-R_2$, which preserves the determinant. Expanding along the new first row givesA square matrix is an invertible matrix exactly when its determinant is nonzero. Thereforeare precisely the three values making $A$ a singular matrix. They also have direct explanations: at $c=0$ the second row is zero, at $c=2$ the first two rows coincide, and at $c=7$ the last two columns coincide.

Let a disk block number and a file number each occupy $h$ bytes. System B spends about $3h$ bytes per physical block on successor/count, predecessor and owner, leaving $B-3h$ payload bytes. It also needs its per-file header. In the traditional inode scheme, file data blocks are entirely payload; indexing occupies the fixed inode and separate indirect blocks.

For $N$ data blocks in a large densely occupied indirect tree, about $N/q$ lowest-level index blocks, $N/q^2$ next-level blocks and so on are needed. With $q=B/h$, the asymptotic indexing space is approximatelyor about $Nh$ bytes when $q$ is large. ThusThis is a comparison of typical densely used structures. For a small file, the fixed inode dominates; near an indirect-level boundary, partly empty index blocks add overhead. Both schemes can waste part of the last block through internal fragmentation.

The main performance advantage is indexed access to an arbitrary file offset: the inode finds the required data block with at most three indirect levels, whereas System B may need to follow a long chain from one end. Index blocks can be cached and scanned in batches, leaving complete data blocks for transfers. The inode scheme also naturally supports sparse files, where absent data-block pointers represent zero-filled holes without allocating every intervening block.

There are additional costs. A cold lookup can require separate index-block reads, allocation near a boundary can require allocating and updating several index blocks, and small files can pay more fixed metadata cost. System B already has a tail pointer and can append with local chain updates, while its owner and predecessor fields can help recovery from surviving blocks. Losing a UNIX indirect block can disconnect many data blocks, and those blocks do not automatically carry System B's owner information. Thus the space and file offset access advantages do not imply uniformly cheaper updates or uniformly better recovery.

A traditional UNIX-like file system identifies a computer file by an inode number. Its inode records file metadata, such as byte length, ownership and permissions, and contains direct file data block addresses plus indirect block pointers. A file-system directory maps a name to the inode number; the filename need not be stored inside the inode.

In the familiar direct/single/double/triple scheme, a single indirect block pointer reaches a block of data-block addresses, a double indirect block pointer reaches blocks of those addresses, and a triple indirect block pointer adds one more level. If there are $d$ direct pointers, one pointer of each indirect level, block size $B$ bytes and pointer width $h$ bytes, put $q=\lfloor B/h\rfloor$. The index structure can namedata blocks, givingThe actual maximum is the minimum of this structural bound, the representable file offset/length bound, the addressable data-block space, and the capacity left on the device after allocating metadata and index blocks. For an unsigned $\ell$-bit byte-length field, its bound is $2^{\ell }-1$ bytes. An empty computer file is permitted and needs no data blocks in this scheme. Exact numerical limits cannot be given without the inode layout and field widths; different UNIX-like implementations choose different layouts, and some use extent trees rather than this traditional scheme.

The predecessor disk block number turns the forward chain into a doubly linked list. Starting from the header's last block, one can traverse backwards; removing or detaching the current block can find its predecessor directly rather than scanning from the beginning. When modifying a chain, the affected predecessor and successor links must both be updated consistently.

The file number identifies the owner of each file data block. A file-system consistency checker can scan the medium, group blocks by owner, detect a cross-link between different files, and help reconstruct chains or headers after damage. It also lets the system check that a block reached through a chain belongs to the expected file.

ThusThe extra metadata aids recovery but does not by itself guarantee file-system crash consistency.

This is linked file allocation. A file header holds the first and last disk block numbers, and the successor field in each block extends the chain. The header therefore does not impose a fixed small maximum number of blocks per file.

To state a numerical bound, suppose a physical block has $B$ bytes, the successor-or-final-count field occupies $h$ bytes, and $N$ distinct data blocks are both addressable and available. A full block then holds $C=B-h$ payload bytes. If the final count can represent every value up to $C$,A smaller computer file can use an arbitrary number of full payload blocks followed by a partial block, so allocation need not be contiguous. With a $p$-bit disk block number, $N\le 2^p$, reduced by reserved addresses and blocks consumed by other data and metadata. This gives the address-width bound as well as the actual device-space bound.

There is no positive minimum payload size: an empty computer file can be represented by an empty-chain convention or a zero-count terminal block. The question does not specify which representation is used or the relevant field widths, so it does not determine an absolute byte limit or a particular empty-file encoding. Its description presupposes a convention that distinguishes a successor value from a terminal byte count.

Reusing a block-oriented file system preserves existing operating-system interfaces, tools, consistency procedures and on-disk formats. It also permits common buffering and caching policies. Large transfers can still amortize software and controller overhead, and flash memory itself has page-program and erase-block constraints, so a block device abstraction is often useful even without mechanical motion.

The costs are that a fine-grained change may require reading and rewriting a larger logical block, and a small computer file can waste part of its final file data block. Structures optimized to reduce seek time need not be best for non-volatile memory. For flash memory, repeated metadata updates and erasing or relocating larger regions can increase physical writes and consume finite program/erase endurance. A translation layer can hide these constraints but adds mapping space and work.

ConsequentlyThe balance depends on the actual medium: byte-addressable non-volatile memory and page/erase-based flash memory have different physical constraints.

A hard disk drive pays substantial seek time to position the head and rotational latency to reach the desired sector. After that positioning, neighboring bytes stream past the head quickly. A larger transfer therefore amortizes positioning and command overhead over many bytes.

The physical sector also needs framing, synchronization and error-correcting redundancy. Transferring one byte at a time would spend an excessive fraction of the medium and controller work on that overhead. A controller buffer and a block transfer can efficiently deliver the sector to computer memory, often using direct memory access.

ThusThe choice is a compromise: excessively large blocks waste transfer time for small requests and can increase internal fragmentation in a file system.

Decompose the 32-bit pattern of $n$ into bytes:Let $x_j=256j+b_j$ be its ten-bit encoding, so $E(x_j)=b_j{2}^{8j}$. The following custom-ISA assembly language sequence implements the requested sum:

addi t,s,x0
addi t,t,x1
addi t,t,x2
addi t,t,x3

The symbols x0 through x3 stand for the encoded ten-bit fields, not for the expanded 32-bit values. After line $j+1$, the destination contains $R_s+{\sum }_{i=0}^j{b}_i{2}^{8i}$ modulo $2^{32}$. HenceIf $t=s$, each instruction correctly uses the preceding partial sum. Zero-byte additions can be omitted except that, when $t\ne s$, an initial instruction must still copy the original source if all earlier omitted bytes are zero. An assembler can initialize t with add t,s,0 instead and then emit only nonzero lanes. If $t=0$, the intended register effect is discarded.

For a MIPS instruction lw t,k(s), first construct $R_u=R_s+{\mathrm{signextend}}_{16}(k)$ in a scratch processor register $u$, using the four-lane sequence above with destination $u$, and then issue

load t,(u)

For sw t,k(s), construct the same address in $u$ and issue

store t,(u)

Choose $u\ne 0,s,t$, or preserve a live scratch processor register according to the calling convention. In particular the store sequence must retain the original data in $t$, even when $s=t$. Both expansions need at most five custom instructions and have the same address and memory-word effects as the corresponding MIPS instructions, assuming aligned valid memory and 32-bit modular address arithmetic. When $k=0$, the memory instruction alone suffices. These are listings for the examination's custom instruction set architecture, not native MIPS encodings; exact exception and pipeline behavior is outside the specified datapath.

The addi immediate operand is a byte-lane immediate: an unsigned eight-bit quantity shifted by $0,8,16$ or $24$ positions. ThusIt is not the sign extension of a 16-bit constant used by the MIPS instruction addi. For example, this design can add $0x12000000$ directly, but cannot add $0x00000123$ in a single immediate instruction. A field containing byte $\mathtt{FF}$ in the low lane adds 255, not $-1$.

The load and store memory address is exactly the content of $r_s$. The arithmetic logic unit result is not connected to the memory-address input. ThereforeThere is no native base-plus-offset calculation during either memory instruction. The paper does not specify exception behavior for signed overflow, so the representable constants and address calculation are the justified differences; the datapath alone cannot establish MIPS-compatible overflow traps.

Choose ToAlu=0 for the $va{l}_t$ input and ToAlu=1 for the expanded immediate operand. Choose ToReg=0 for the arithmetic logic unit result and ToReg=1 for memory read data. The diagram does not label the multiplexer polarities, so these are explicit conventions.

Let $F_{+}$ and $F_{\vee }$ denote the six-bit arithmetic logic unit operation codes for addition and bitwise OR. Their numerical codes are not specified by the paper. The opcode needs to distinguish register, immediate, load and store modes; add and or can share register mode, and addi and ori can share immediate mode, since $15:10$ selects the operation directly. For example, choose $o_R=000000$, $o_I=000001$, $o_L=000010$ and $o_S=000011$. With $X$ denoting a field whose bits do not matter, the formats are:

The required opcode control table is:

Here MemRd is irrelevant whenever read data is unused, under the ordinary side-effect-free memory interpretation of the diagram. It is sensible to choose zero for those $X$ entries to save activity; memory-mapped devices with read side effects would require that choice. For store, ToReg is irrelevant because $r_d=0$; ToAlu is essential because its output supplies both the second arithmetic logic unit operand and memory write data. For load, the memory address is $va{l}_s$ independently of ToAlu and of $15:10$.

The resulting effects, with 32-bit addition, arewhere $E(x)=(x\mathrm{mod}256)2^{8\lfloor x/256\rfloor }$ for the ten-bit field $x$.